高层次综合的算子调度与寄存器分配

高层次综合技术是CPU、DSP等复杂结构设计中的关键技术,对于超大规模集成电路设计有重要的指导意义。本文深入探讨了高层次综合技术,并对高层次综合的核心技术-算子调度算法和寄存器分配算法进行分析。常用的算子调度算法有表格调度算法和FDS算法等。寄存器分配主要根据寄存器资源的生命周期对寄存器进行复用设计。     

一种可测性调度分配方法

提出一种基于演化算法的可测性调度分配方法.应用演化算法,在调度和分配过程中研究电路的可测性设计.该方法的贡献是:给出了三个可测性准则;设计了可测性目标函数;提出了一种新颖的演化编码和演化操作,提高了搜索速度和解的质量.实验结果验证了该方法的可行性.     

一种同时实现算子调度与数据流图划分的高层次综合算法

选择分模块的数据通道作为高层次综合的目标结构,完整地定义了同时实现算子调度和数据流图划分的高层次综合算法,并提出一种有效的启发式求解方法.与传统的结构相比,由于在关键路径中消除了全局连线的延时,分模块的结构可以有效地减小时钟周期、优化电路性能.实验结果验证了该方法的有效性.     

一种同时实现算子调度与数据流图划分的高层次综合算法

选择分模块的数据通道作为高层次综合的目标结构,完整地定义了同时实现算子调度和数据流图划分的高层次综合算法,并提出一种有效的启发式求解方法.与传统的结构相比,由于在关键路径中消除了全局连线的延时,分模块的结构可以有效地减小时钟周期、优化电路性能.实验结果验证了该方法的有效性     

一种改进公交调度算法的研究

智能公交调度是一个复杂的非线性问题,利用遗传算法,可以很大程度上减少检索次数,同时引入了一种改进的遗传算法,它在已有的算法诸优点的基础之上,将它们和各种优秀遗传算子综合在一个GA结构中,从而构建了公共交通线线路发车间隔优化模型,解决了智能公交中的线网间智能调度的难题,该模型和算法在模拟中和实际情况一致,获得了较好的调度优化效果。     

多目标约束的网格任务安全调度模型及算法研究

异构网格环境的特点决定了其任务调度是受调度长度、安全性能及调度费用等多个因素制约的。该文根据网格资源调度的特点构造了一个安全效益函数和节点信誉度动态评估模型,并以此为基础建立了一个多目标约束的网格任务调度模型。利用隶属度函数将多目标函数转化为单目标模型,通过设计新的进化算子,从而提出一种遗传算法MUGA(Mode Crossover and Even Mutation Genetic Algorithm)进行求解,并对算法的收敛性进行了理论分析。仿真实验表明,在同等条件下该算法与同类算法相比,在任务调度长度、安全效益值、可信度及调度费用指标优化方面具有较好的综合性能。     

时间约束条件下改进力向调度算法

集成电路自动化设计中,算子调度是其核心问题之一。为了使系统资源分配合适,资源耗费最小,在现有力向调度算法上提出了在时间约束条件下的改进算法。该算法将各算子之间的前后级联关系采用关联概率表征,提高了运行速度。对多种样例进行测试,并与现有方法进行实验对比。结果表明,改进后的算法在保证调度方案效果的同时,大大减少了计算量。     

H.264中DCT算法在FPGA上的高层次综合实现

针对传统硬件设计方法在大规模算法应用实现中的高复杂度,提出了一种高层次综合方法,从而实现高效快速地硬件设计。以H.264编码中常用的DCT算法的硬件实现为目的,对算法的C语言实现进行优化,并使用高层次综合工具将优化后的C语言算法描述转换为专用硬件加速器;通过高层次综合工具提供的接口设定、流水线插入、块并行等操作,对生成的硬件作进一步优化;与人为DCT算法的RTL设计和采用高层次综合方法的DCT硬件设计相比,具有更大的设计空间和更高的代码可裁剪性。FPGA实现结果表明,H.264中基于高层次综合方法的DCT算法在节省大量设计开发时间的前提下,可达到每秒处理516兆个整型数的计算性能。     

基于JTAG的电路板可测性设计分析技术

电路板的可测性和设计复杂性是一对矛盾,由此提出了基于网络表文件的可测性设计优化算法,可在改善电路板测试性的同时,最大限度地降低电路板的设计复杂性.该算法用Matlab来实现,通过对电路板网络表文件的数学分析,确定用最少的边界扫描器件实现对电路网络的一个最大覆盖,从而改善电路板的测试性,大幅度提高电路板的测试覆盖率.最后,利用算法对某电路板进行了可测性分析,试验表明对器件进行了有效的定位,从而为设计工程师进行可测性设计提供了参考和方向.     

基于改进遗传算法的网格资源调度算法

网格计算关注大规模的资源和任务调度，要求采用的调度算法能够具有高效性。提出一种基于改进遗传算法的资源调度算法，该算法综合考虑了资源任务分配量以及任务完成时间，从而设计出良好的交叉和选择算子，既能够保留完成时间比较小的个体又能够保留具有一部分优秀资源分配方式的个体．算法具有较好的效率和收敛性。     

作业车间调度问题的多种群遗传算法

针对最小化完工时间的作业车间调度问题提出一个多种群遗传算法,该算法基于工艺约束定义个体的编码方式,基于工件操作构造遗传算子,保证了所有个体的可行性;多种群算法通过各个种群之间的相互竞争和良种共享,提高了资源的利用效率,有效地克服个体早熟,改善了算法的收敛性能.典型测试算例表明该算法是非常有效的.     

基于功能单元最大利用率的调度算法

高级综合中调度决定系统运行速度与造价的折衷，调度问题为ＮＰ问题。本文将调度问题看作为多目标优化问题，并提出一种基于功能单元最大利用率的调度算法，以较低的时间复杂度求得调度问题的最优或近似最优解，该算法不仅可求解时间约束下的调度问题，也可求解造价约束下的调度问题。     

Unifiable scheduling and allocation for minimizing system cycletime

This paper describes a new scheduling and allocation algorithm which optimizes a datapath-controller system for clock cycle time. The cycle time of a VLSI system depends not only on the characteristics of the datapath and controller in isolation but also on the interactions between them. A datapath may impose both arrival time constraints on controller inputs and departure time constraints on controller outputs. Late-arriving controller inputs may be generated by complex datapath functions, such as ALU carry-out, while early-departure controller outputs may be required to control slow datapath units. If the controller is not designed taking into account arrival and departure times, it may unnecessarily put control logic on the critical timing path. Our synthesis heuristic, which can be used in conjunction with other scheduling heuristics, identifies critical interactions between datapath and controller and reallocates/reschedules them to reduce system cycle time during high-level synthesis. Experimental results show that a unifiable scheduling and allocation (USA) can substantially improve system cycle time with only small area penalties     

Stochastic job stream scheduling method for cipher chip with multi-cryptography

Aiming at the rich of safety requirements of tasks which resulting in random cross access to multi cipher algorithms, a hierarchical hardware scheduling method was presented with associated control based on data identifica-tion. The first level was responsible for distributing tasks to different cipher clusters, and by optimizing the search logic to achieve rapid distribution of data. The second level was responsible for completing the context-related tasks in scheduling order by adding an association control module and association queues. Intermediate state storage module realized the saving of the intermediate state in serial cipher algorithm modes, which was indexed by task ID. Pre-processing module process data inputted by the succeeding tasks. It is proved that the proposed scheduling algo-rithm solves the problem of random cross encryption and decryption in many-to-many communication model of high-speed data stream.     

一种数字电路高层综合器DCS

本文介绍一种数字电路综合器ＤＣＳ，重点讨论数据流分配及控制时序的实现。其中，操作符分配采用团划分算法，连线分配采用基于规则的方法，控制器综合采用基于计数器的设计方法。     

基于树型网格的混合遗传算法

资源调度算法是网格计算研究的一个重要研究方向。文章讨论了树型网格的逻辑调度模式．提出了基于树型网格的混合遗传算法HGATG。算法利用启发式操作算子加快最优值的收敛速度．并采用随机法和唯一法来避免算法的早熟。实验结果表明HGATG算法在求解速度、成功率和求解问题的规模等方面有较好的效果。     

基于遗传算法的无向图多划分优化

文章描述了无向图多划分的优化问题,提出了一个基于遗传算法的图的多划分优化方法.该方法针对无向图多划分的特点,分别对适应度函数、遗传操作算子以及参数选取等方面进行了改进.实际研究结果表明该算法实现了无向图多划分优化的目的.     

Scheduling and allocation in high-level synthesis using stochastic techniques

High-level synthesis is the process of automatically translating abstract behavioral models of digital systems to implementable hardware. Operation scheduling and hardware allocation are the two most important phases in the synthesis of circuits from behavioral specification. Scheduling and allocation can be formulated as an optimization problem. In this work, a unique approach to scheduling and allocation problem using the genetic algorithm (GA) is described. This approach is different from a previous attempt using GA (Wehn et al., IFIP Working Conference on Logic and Architecture Synthesis, Paris, 1990, pp. 47–56) in many respects. The main contributions include: (1) a new chromosomal representation for scheduling and for two subproblems of allocation; and (2) two novel crossover operators to generate legal schedules. In addition the application of tabu search (TS) to scheduling and allocation is also implemented and studied. Two implementations of TS are reported and compared. Both genetic scheduling and allocation (GSA) and tabu scheduling and allocation (TSA) have been tested on various benchmarks and results obtained for data-oriented control-data flow graphs are compared with other implementations in the literature. (A discussion on GSA was presented at the European Design Automation Conference Euro-DAC'94 in Grenoble, France, and TSA at the International Conference on Electronics, Circuits and Systems — ICECS'94 in Cairo, Egypt.) A novel interconnect optimization technique using the GA is also realized.     

A game theoretic approach for power optimization during behavioral synthesis

In this paper, we describe a new methodology based on game theory for minimizing the average power of a circuit during scheduling and binding in behavioral synthesis. The problems are formulated as auction-based noncooperative finite games for which solutions are proposed based on the Nash equilibrium. In the scheduling algorithm, a first-price sealed-bid auction approach is used while, for the binding algorithm, each functional unit in the datapath is modeled as a player bidding for executing an operation with the estimated power consumption as the bid. Further, the techniques of functional unit sharing, path balancing, and register assignment are incorporated within the binding algorithm for power reduction. The combined scheduling and binding algorithm is formulated as a single noncooperative auction game with the functional units in the datapath modeled as players bidding for executing the operation in a particular control cycle. The proposed algorithms yield power reduction without any increase in area overhead and only a slight increase in the latency for some of the benchmark circuits. Experimental results indicate that the proposed game theoretic solution for binding yields an improvement of 13.9% over the linear programming (LP) method, while the scheduling and the combined scheduling and binding algorithms yield average improvements of 6.3% and 11.8%, respectively, over the integer-linear programming (ILP) approach.     

Synthesis of Hard Real-Time Application Specific Systems

This paper presents a system level approach for the synthesis of hard real-time multitask application specific systems. The algorithm takes into account task precedence constraints among multiple hard real-time tasks and targets a multiprocessor system consisting of a set of heterogeneous off-the-shelf processors. The optimization goal is to select a minimal cost multi-subset of processors while satisfying all the required timing and precedence constraints. There are three design phases: resource allocation, assignment, and scheduling. Since the resource allocation is a search for a minimal cost multi-subset of processors, we adopted an A* search based technique for the first synthesis phase. A variation of the force-directed optimization technique is used to assign a task to an allocated processor. The final scheduling of a hard-real time task is done by the task level scheduler which is based on Earliest Deadline First (EDF) scheduling policy. Our task level scheduler incorporates force-directed scheduling methodology to address the situations where EDF is not optimal. The experimental results on a variety of examples show that the approach is highly effective and efficient.