共查询到20条相似文献,搜索用时 46 毫秒
1.
2.
An efficient partitioning algorithm for mixed-mode placement,extended-MFFC-based partitioning,is presented.It combines the bottom-up clustering and the top-down partitioning together.To do this,designers can not only cluster cells considering logic dependency but also partition them aiming at min-cut.Experimental results show that extended-MFFC-based partitioning performs well in mixed-mode placement with big pre-designed blocks.By comparison with the famous partitioning package HMETIS,this partitioning proves its remarkable function in mixed-mode placement. 相似文献
3.
针对可重构计算机系统配置次数(划分块数)的最小化问题,提出了一种融合面积估算和多目标优化的硬件任务划分算法。该算法每次划分均进行硬件资源面积的估算,并且通过充分考虑可重构资源的使用、一个数据流图所有划分块执行延迟总和、划分模块间边数等因素构造了新的探测函数prior_assigned(),该函数能够计算每个就绪节点的优先权值,新算法通过该值能动态调整就绪列表任务节点的调度次序。实验结果表明,与现有的层划分、簇划分、增强静态列表、多目标时域划分、簇层次敏感等5种划分算法相比,该算法能获得最少的模块数,并且随着可重构处理单元面积的增大,除层划分算法之外,其执行延迟的均值也是最小的。 相似文献
4.
Yu-Liang Wu Chak-Chung Cheung Cheng D.I. Hongbing Fan 《Very Large Scale Integration (VLSI) Systems, IEEE Transactions on》2003,11(3):451-460
Efficient circuit partitioning is becoming more and more important as the size of modern circuits keeps increasing. Conventionally, circuit partitioning is solved without altering the circuit by modeling the circuit as a hypergraph for the ease of applying graph algorithms. However, there is room for further improvement on even optimal hypergraph partitioning results, if logic information can be applied for circuit perturbation. Such logic transformation based partitioning techniques are relatively less addressed. In this paper, we present a powerful multiway partitioning technique which applies efficient logic rewiring techniques for further improvement over already superior hypergraph partitioning results. The approach can integrate with any graph partitioner. We perform experiments on two-, three-, and four-way partitionings for MCNC benchmark circuits whose physical and logical information are both available. Our experimental results show that this partitioning approach is very powerful. For example, it can achieve a further 12.3% reduction in cut size upon already excellent pure graph partitioner (hMetis) results on two-way partitioning with an area penalty of only 0.34%. The outperforming results demonstrate the usefulness of this new partitioning technique. 相似文献
5.
Jianhua Li Behjat L. 《Circuits and Systems II: Express Briefs, IEEE Transactions on》2006,53(5):384-388
Circuit partitioning is a fundamental problem in very large-scale integration (VLSI) physical design automation. In this brief, we present a new connectivity-based clustering algorithm for VLSI circuit partitioning. The proposed clustering method focuses on capturing natural clusters in a circuit, i.e., the groups of cells that are highly interconnected in a circuit. Therefore, the proposed clustering method can reduce the size of large-scale partitioning problems without losing partitioning solution qualities. The performance of the proposed clustering algorithm is evaluated on a standard set of partitioning benchmarks-ISPD98 benchmark suite. The experimental results show that by applying the proposed clustering algorithm, the previously reported best partitioning solutions from state-of-the-art partitioners are further improved. 相似文献
6.
7.
Srinivasan V. Govindarajan S. Vemuri R. 《Very Large Scale Integration (VLSI) Systems, IEEE Transactions on》2001,9(1):140-158
Reconfigurable computers (RCs) host multiple field programmable gate arrays (FPGAs) and one or more physical memories that communicate through an interconnection fabric. State-of-the-art RCs provide abundant hardware and storage resources, but have tight constraints on FPGA pin-out and inter-FPGA interconnection resources. These stringent constraints are the primary impediment for multi-FPGA partitioning tools to generate high-quality designs, in this paper, we present two integrated partitioning and synthesis approaches for RCs. The first approach involves fine-grained partitioning of a scheduled data-flow graph (DFG, or an operation graph), and the second involves a coarse-grained partitioning of an unscheduled control data flow graph (CDFG, or a block graph). A hardware design space exploration engine is integrated with the block graph partitioner that dynamically contemplates multiple schedules during partitioning. The novel feature in the partitioning approaches is that the physical memory in the RC is effectively used to alleviate the FPGA pin-out and inter-FPGA interconnection bottle-neck. Several experiments have been conducted, targeting commercial multi-FPGA boards, to compare the two partitioning approaches, and detailed summaries are presented 相似文献
8.
本文以MLC系统各等价信道的信道容量为依据[1],选用不同码长的BCH码系列作为MLC系统中各级的分量码,通过计算机模拟,比较了三种不同的集分割方法所构成的MLC/MSD方案,分别在AWGN和Rayleigh衰落信道中、8ASK调制方式下的性能.模拟结果表明:UP分割在AWGN信道中具有最好的性能;BP分割可自适应于AWGN和Rayleigh衰落混合的移动衰落信道,是MLC方案应用于移动衰落信道中的最佳集分割方案. 相似文献
9.
System Level Hardware/Software Partitioning Based on Simulated Annealing and Tabu Search 总被引:18,自引:1,他引:17
Petru Eles Zebo Peng Krzysztof Kuchcinski Alexa Doboli 《Design Automation for Embedded Systems》1997,2(1):5-32
This paper presents two heuristics for automatic hardware/software partitioning of system level specifications. Partitioning is performed at the granularity of blocks, loops, subprograms, and processes with the objective of performance optimization with a limited hardware and software cost. We define the metric values for partitioning and develop a cost function that guides partitioning towards the desired objective. We consider minimization of communication cost and improvement of the overall parallelism as essential criteria during partitioning. Two heuristics for hardware/software partitioning, formulated as a graph partitioning problem, are presented: one based on simulated annealing and the other on tabu search. Results of extensive experiments, including real-life examples, show the clear superiority of the tabu search based algorithm. 相似文献
10.
Extending the Kernighan/Lin Heuristic for Hardware and Software Functional Partitioning 总被引:5,自引:0,他引:5
The Kernighan/Lin graph partitioning heuristic, also known as min-cut or group migration, has been extended over several decades very successfully for circuit partitioning. Those extensions customized the heuristic and its associated data structure to rapidly compute the minimum-cut metric central to circuit partitioning; as such, those extensions are not directly applicable to other problems. In this paper, we extend the heuristic for functional partitioning, which in turn can solve the much investigated codesign problem of partitioning a system's coarse-grained functions among hardware and software components. The key extension customizes the heuristic and data structure to rapidly compute execution-time and communication metrics, crucial to hardware and software partitioning, and leads to near-linear time-complexity and excellent resulting quality. Another extension uses a new criteria for terminating the heuristic, eliminating time-consuming and unnecessary fine-tuning of a partition. Our experiments demonstrate extremely fast execution times (just a few seconds) with results matched only by the slower simulated annealing heuristic, meaning that the extended Kernighan/Lin heuristic will likely prove hard to beat for hardware and software functional partitioning. 相似文献
11.
Soumik Sarkar Kushal Mukherjee Xin Jin Dheeraj S. Singh Asok Ray 《Signal processing》2012,92(3):625-635
The concept of symbolic dynamics has been used in recent literature for feature extraction from time series data for pattern classification. The two primary steps of this technique are partitioning of time series to optimally generate symbol sequences and subsequently modeling of state machines from such symbol sequences. The latter step has been widely investigated and reported in the literature. However, for optimal feature extraction, the first step needs to be further explored. The paper addresses this issue and proposes a data partitioning procedure to extract low-dimensional features from time series while optimizing the class separability. The proposed procedure has been validated on two examples: (i) parameter identification in a Duffing system and (ii) classification of fatigue damage in mechanical structures, made of polycrystalline alloys. In each case, the classification performance of the proposed data partitioning method is compared with those of two other classical data partitioning methods, namely uniform partitioning (UP) and maximum entropy partitioning (MEP). 相似文献
12.
13.
本文提出了一种改进的层划分算法.该算法充分考虑了划分块的最小执行延迟和尽可能充分利用可重构资源,能够跟踪层划分算法节点分配过程并进行调整,消除了经典层划分算法不能动态更新就绪节点列表选取节点进行划分的缺陷.实验结果表明,与层划分算法相比,所提出的改进层划分算法在模块数、执行延迟和跨模块间的I/O边数等三个方面均获得了改进.与现有的簇划分、增强静态列表、多目标时域划分、簇层次敏感等四种划分算法相比,新算法能获得最少的执行延迟,并且随着可重构处理单元面积的增大,模块数的均值也是最小的. 相似文献
14.
We investigate the optimal partitioning of the end-to-end network QoS budget to quantify the advantage of having a non-uniform allocation of the budget over the links in a path. We formulate an optimization problem that provides a unified framework to study QoS budget allocation. We examine the underlying mathematical structure for the optimal partitioning and dimensioning equations. In the context of network dimensioning, we then show that optimal partitioning can bring large cost reductions as compared with equal partitioning based on the results on small networks. More importantly, we also find that optimal partitioning gives significant improvements in robustness in the presence of failed components and in fairness when the traffic demand is different from the forecast, two effects that had not been observed in previous work and that can have a significant effect on network operations. 相似文献
15.
推测多线程主要针对编译器生成的指令进行线程划分,在控制流和数据流分析基础上,实现串行程序的自动并行化.模拟器作为检验线程划分算法的有效手段,不仅能验证程序执行结果的正确性,而且可以评估程序并发执行的加速比性能,进一步也可以反映线程划分算法的合理性.针对Olden Suite程序在模拟器上的运行时统计信息,分析线程划分中所存在的寄存器依赖问题.同时,结合实例详细讨论造成寄存器依赖的主要原因.最后,针对寄存器依赖问题提出一种改进的线程划分方法. 相似文献
16.
For real-time communication services to achieve widespread usage, it is important that network managers be allowed to control the services effectively. An important management capability concerns resource partitioning. Resource partitioning is useful for a number of applications, including the creation of virtual private subnetworks and of mechanisms for advance reservation of real-time network services, fast establishment of real-time connections, and mobile computing with real-time communication. In previous work, the authors presented a scheme for resource partitioning in a guaranteed performance networking environment with EDD-based packet scheduling disciplines. The present paper gives the results of research in resource partitioning, with admission control tests for resource partitioned servers for four representative scheduling disciplines, FIFO, WFQ, RCSP and EDD. The simulations confirm the intuition that resource fragmentation losses due to resource partitioning are small and that resource partitioning reduces the admission control computation overhead. An interesting result from the simulation experiments is that, under circumstances that arise naturally in multi-party communication scenarios, resource partitioning results in higher overall connection acceptance rate. The authors also present experiences with implementing resource partitioning in the second generation of Tenet real-time protocols; this implementation, with resource partitioned servers, runs on multiple platforms, including Sun workstations under SunOS, DEC workstations under Ultrix, and PCs under BSDI Unix 相似文献
17.
Zhenyu Sun Tjeng Thiang Tjhung 《Wireless Communications, IEEE Transactions on》2007,6(7):2374-2378
Proper partitioning of a unitary space-time (UST) signal set is essential for the optimal design of trellis coded unitary space-time modulation (TC-USTM). The unique properties of these UST signals have necessitated a different partitioning methodology from that of the conventional two dimensional constellations. In this letter, we propose a systematic set partitioning through a novel subset-pairing strategy, for an arbitrary UST signal set. This approach leads to a geometrically congruent partitioning, i.e., subsets of the same size (order) have identical intra-distance profiles. Based on this partitioning, the resulting TC-USTM can achieve a minimum bit error probability. 相似文献
18.
An Algorithm for Hardware/Software Partitioning Using Mixed Integer Linear Programming 总被引:6,自引:1,他引:5
One of the key problems in hardware/software codesign is hardware/software partitioning. This paper describes a new approach to hardware/software partitioning using integer programming (IP). The advantage of using IP is that optimal results are calculated for a chosen objective function. The partitioning approach works fully automatic and supports multi-processor systems, interfacing and hardware sharing. In contrast to other approaches where special estimators are used, we use compilation and synthesis tools for cost estimation. The increased time for calculating values for the cost metrics is compensated by an improved quality of the values. Therefore, fewer iteration steps for partitioning are needed. The paper presents an algorithm using integer programming for solving the hardware/software partitioning problem leading to promising results. 相似文献
19.
20.
一种基于伪LRU的新型共享Cache划分机制 总被引:1,自引:0,他引:1
本文提出了一种基于伪LRU方法的新型共享Cache动态划分策略PLRU-SCP.本文提出的划分策略在分析电路中给出了基于二叉树的新型分析方法,在划分电路中使用了一种非遍历的划分算法.并提出了一种新型共享Cache结构.本文提出的新型划分策略比基于LRU方法的不划分共享Cache策略和效用最优的划分策略的性能分别提高了11.05%和8.66%. 相似文献