...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Pomiary Automatyka Kontrola >Selekcja klas kompatybilności z zastosowaniem teorii hipergrafów
【24h】

Selekcja klas kompatybilności z zastosowaniem teorii hipergrafów

机译：使用超图理论选择相容性类别

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Redukcja pojemności pamięci jest istotnym etapem w procesie projektowania systemów dyskretnych. Często pojemność prototypowanej pamięci przekracza rozmiar docelowego bloku pamięci (np. w układach programowalnych FPGA). Najczęściej stosowanym rozwiązaniem jest redukcja rozmiaru mikroinstrukcji w projektowanym systemie. Algorytm bazuje na wyznaczeniu, a następnie selekcji klas kompatybilności poszczególnych mikrooperacji. W artykule zaprezentowane zostaną 2 autorskie algorytmy selekcji klas kompatybilności. Metody opierają się o wykorzystanie teorii hipergrafów (zastosowanie pokrycia wierzchołkowego). Proponowane rozwiązania zostaną gruntownie przeanalizowane oraz porównane z metodą tradycyjną, bazują na przekształceniach macierzowych.%The problem of memory size reduction is a very important part of design process of discrete systems. The prototyped memory size very often exceeds the size of memory blocks offered by programmable devices (in example FPGAs). One of the most popular solutions to this problem is memory size reduction. The reduction process is based on selection of the compatibility classes of microoperations. Three methods of selection of compatibility classes are presented in the paper. The first one is a well-known method of selection, to which the fast reduction algorithm is applied. The algorithm bases on the matrix operations, which can also be represented as reduction of the hypergraph incidence matrix. In each step some vertices and edges are reduced. The reduced matrix holds the final result. The two other solutions introduced in the paper are based on the idea of computation of the minimal transversal (vertices covering) of hypergraphs. Proper microoperations are represented by the hypergraph vertices, while compatibility classes are described by the hyperedges. Therefore, any method of hypergraph transversal calculation can be applied to achieve the selection. In the paper the authors propose and analyse the effectiveness of backtracking and greedy algorithms. The proposed solutions are compared with the traditional method, which is based on transformation of the hypergraph incidence matrix. The obtained results of experiments are analysed and discussed in detail.
机译：减少内存容量是离散系统设计过程中的重要步骤。原型存储器的容量通常超过目标存储器块的大小（例如在FPGA可编程电路中）。最常用的解决方案是减小设计系统中微指令的大小。该算法基于各个微操作的兼容性类别的确定和后续选择。本文介绍了2种用于选择兼容性类的专有算法。这些方法基于超图理论的使用（顶端覆盖的使用）。提出的解决方案将在矩阵变换的基础上进行深入分析，并与传统方法进行比较，减少存储空间的问题是离散系统设计过程中非常重要的部分。原型存储器的大小通常超过可编程设备（例如FPGA）提供的存储器块的大小。解决此问题的最流行方法之一是减小内存大小。简化过程基于微操作兼容性类的选择。本文提出了三种选择兼容性等级的方法。第一个是众所周知的选择方法，快速还原算法已应用到该方法中。该算法基于矩阵运算，也可以表示为超图入射矩阵的约简。在每个步骤中，都会减少一些顶点和边缘。简化后的矩阵保留最终结果。本文介绍的其他两个解决方案基于超图的最小横向（顶点覆盖）的计算概念。适当的微操作由超图顶点表示，而兼容性类由超边描述。因此，可以应用任何超图横向计算方法来实现选择。在本文中，作者提出并分析了回溯和贪婪算法的有效性。将提出的解决方案与传统方法进行了比较，传统方法基于超图关联矩阵的转换。对获得的实验结果进行了分析和讨论。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号