A Dynamic Data Structure--Pool And Its Application In Intelligent VLSI Circuit Placement Design

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.