【作者】 张徐亮；

【导师】 虞厥邦； 黄劲；

【作者基本信息】 电子科技大学 ， 电路与系统， 2001， 博士

【摘要】 本文提出一个新的数据结构概念——动态数据结构。基于这个概念，本文实现了一种新的数据结构——池及其在一维和二维时的情况。本文同时对这种新的数据结构在VLSI电路布局设计中的应用和在打印机任务调度中的应用进行了研究。 本文的主要贡献概括如下： 1.本文讨论了各种计算机应用中的动态数据处理要求，之后提出了动 态数据结构的概念。根据这一新概念，本文建议了一种新的数据结 构——池，它能对数据进行动态处理（例如，数据的表示，查找， 合并，排序和存储等等）。 2.本文研究了一维池和二维池的实现，对一维池和二维池的顺序存 取、基于周期机制和基于触发机制的动态秩序维持程序进行了研 究，并定义了一维池和二维池的基本运算。 3.本文成功地将池和遗传算法相结合，形成改进的基于池的遗传算法 （PGA），以作为池的一种灵活应用。然后，将基于池的遗传算法 （PGA）用于解决门阵列布局设计。对门阵列布局算例的计算机仿 搞要 真结果表明使用基于池的遗传算法汀GA）能够获得比传统遗传算 法（GA）更好的结果。 4．本文将快速进化规划算法（FEP）用于同样的门阵列布局算例，也 取得了满意的结果。 5．为减小通道布线中线网间的串扰，本文提出一个基于扰动的算法。 我们将此算法运用到若干benchlnn例子上去，并和已知的一些结 果进行了比较，结果表明我们建议的基于扰动的算法能够获得比文 甲 献p7习21更优的性能。 动态数据结构一池是一种普适的工具，可以用来解决其他计算机科学领域中的问题，比如进程管理、并行计算中的任务分配等。作为一个具体的应用，本文将二维池应用到打印机任务调度中，仿真结果表明算法能解决繁重的计算机排队打印问题。更多还原

【Abstract】 A new idea of data structure ?dynamic data structure is proposed in this thesis. Based on this idea, a novel type of data structure 棗 Pool is implemented in 1-dimension and 2-dimension cases. Applications of this novel data structure in VLSI circuit layout and printer task queuing are also studied. Main contributions of the thesis are the following: 1. Demand of dynamic data processing in a variety of computer applications is addressed, a concept of dynamic data structure is then proposed, upon which a novel data structure Pool able to dynamically handle data processing (Such as data representation, searching, merging, ordering and storage, etc.)is suggested. 2. Implementation of 1-D and 2-D pool is described, their sequential data accessing mechanism and dynamic maintenance program, in both periodic and trigger manner, are described, and basic pool operations are also defined. 3. As one of the feasible applications of pooi, we have successfully m Abs~act formulated a modified pool-based genetic algorithni(PGA), then applied it to solve a gate array placement problem. Computer simulation results of an example show that improvement over traditional GA can be nbtained by using our PGA. 4. For the same gate array placement example, we use a fast evolutionary programming (FEP) to get better results. 5. To minimizing crosstalk among nets in channel routing, a perturbation-based algoritlun is proposed. The algorithm is applied to benchmark examples, and comparative simulation results show that our algorithm is more effective than those given in previous literatures [87-92] It is pointed out that the dynamic data structure ?pool is a powerful general-purpose tool to solve a variety of problems in other areas of computer sciences, such as process management, task assignment in parallel computing, etc. As an example, a printer task queuing management algorithm is designed by using 2-D pool, simulation results show that the algorithm is able to solve complicate and heavy duty printer queuing problems.更多还原