Li, Liang. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 57-61). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.1.1 --- Partitioning --- p.1 / Chapter 1.1.2 --- Floorplanning and Placement --- p.2 / Chapter 1.1.3 --- Routing --- p.2 / Chapter 1.1.4 --- Compaction --- p.3 / Chapter 1.2 --- Motivations --- p.3 / Chapter 1.3 --- Problem Formulation --- p.4 / Chapter 1.3.1 --- Properties of OARSMT --- p.4 / Chapter 1.4 --- Progress on the Problem --- p.4 / Chapter 1.5 --- Contributions --- p.5 / Chapter 1.6 --- Thesis Organization --- p.6 / Chapter 2 --- Literature Review on OARSMT --- p.8 / Chapter 2.1 --- Introduction --- p.8 / Chapter 2.2 --- Previous Methods --- p.9 / Chapter 2.2.1 --- OARSMT --- p.9 / Chapter 2.2.2 --- Shortest Path Problem with Blockages --- p.13 / Chapter 2.2.3 --- OARSMT with Delay Minimization --- p.14 / Chapter 2.2.4 --- OARSMT with Worst Negative Slack Maximization --- p.14 / Chapter 2.3 --- Comparison --- p.15 / Chapter 3 --- Heuristic Method --- p.17 / Chapter 3.1 --- Introduction --- p.17 / Chapter 3.2 --- Our Approach --- p.18 / Chapter 3.2.1 --- Handling of Multi-pin Nets --- p.18 / Chapter 3.2.2 --- Propagation --- p.20 / Chapter 3.2.3 --- Backtrack --- p.23 / Chapter 3.2.4 --- Finding MST --- p.26 / Chapter 3.2.5 --- Local Refinement Scheme --- p.26 / Chapter 3.3 --- Experimental Results --- p.28 / Chapter 3.4 --- Summary --- p.28 / Chapter 4 --- Exact Method --- p.32 / Chapter 4.1 --- Introduction --- p.32 / Chapter 4.2 --- Review on GeoSteiner --- p.33 / Chapter 4.3 --- Overview of our Approach --- p.33 / Chapter 4.4 --- FST with Virtual Pins --- p.34 / Chapter 4.4.1 --- Definition of FST --- p.34 / Chapter 4.4.2 --- Notations --- p.36 / Chapter 4.4.3 --- Properties of FST with Virtual Pins --- p.36 / Chapter 4.5 --- Generation of FST with Virtual Pins --- p.46 / Chapter 4.5.1 --- Generation of FST with Two Pins --- p.46 / Chapter 4.5.2 --- Generation of FST with 3 or More Pins --- p.48 / Chapter 4.6 --- Concatenation of FSTs with Virtual Pins --- p.50 / Chapter 4.7 --- Experimental Results --- p.52 / Chapter 4.8 --- Summary --- p.53 / Chapter 5 --- Conclusion --- p.55 / Bibliography --- p.61

Ma, Tilen. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2007. / Includes bibliographical references (leaves 98-100). / Abstracts in English and Chinese. / Abstract --- p.i / Chapter 0.1 --- Abstract --- p.i / Acknowledgement --- p.iv / Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Physical Design Cycle --- p.2 / Chapter 1.2 --- Floorplanning --- p.6 / Chapter 1.2.1 --- Floorplanning Objectives --- p.7 / Chapter 1.2.2 --- Common Approaches --- p.8 / Chapter 1.3 --- Motivations and Contributions --- p.11 / Chapter 1.4 --- Organization of the Thesis --- p.13 / Chapter 2 --- Literature Review on Placement Constraints in Floorplanning --- p.15 / Chapter 2.1 --- Introduction --- p.15 / Chapter 2.2 --- Algorithms for Abutment Constraint --- p.16 / Chapter 2.3 --- Algorithms for Alignment Constraint --- p.18 / Chapter 2.4 --- Algorithms for Boundary Constraint --- p.20 / Chapter 2.5 --- Unified Approach for Placement Constraints --- p.23 / Chapter 2.5.1 --- Representation of Placement Constraints --- p.23 / Chapter 2.5.2 --- Handling Relative Placement Constraints --- p.24 / Chapter 2.5.3 --- Examples for Handling Placement Constraints --- p.25 / Chapter 3 --- Literature Review on Bus-Driven Floorplanning --- p.28 / Chapter 3.1 --- Introduction --- p.28 / Chapter 3.2 --- Previous Work --- p.28 / Chapter 3.2.1 --- Zero-Bend Bus-Driven Floorplanning [3] --- p.28 / Chapter 3.2.2 --- Two-Bend Bus-Driven Floorplanning [1] --- p.32 / Chapter 4 --- Placement Constraints for Multi-Bend Bus in TCGs --- p.38 / Chapter 4.1 --- Introduction --- p.38 / Chapter 4.2 --- Transitive Closure Graph [6] --- p.39 / Chapter 4.3 --- Placement Constraints for Zero-Bend Bus --- p.41 / Chapter 4.4 --- Placement Constraints for Multi-Bend Bus --- p.44 / Chapter 4.5 --- Placement Constraints for Bus Ordering --- p.45 / Chapter 4.5.1 --- Natural Bus Ordering in TCGs --- p.45 / Chapter 4.5.2 --- Explicit Bus Ordering in TCGs --- p.46 / Chapter 5 --- TCG-Based Bus-Driven Floorplanning --- p.48 / Chapter 5.1 --- Motivation --- p.48 / Chapter 5.2 --- Problem Formulation --- p.49 / Chapter 5.3 --- Methodology --- p.50 / Chapter 5.3.1 --- Construction of Reduced Graphs --- p.51 / Chapter 5.3.2 --- Construction of Common Graph --- p.52 / Chapter 5.3.3 --- Spanning Tree for Bus Assignment --- p.53 / Chapter 5.3.4 --- Formation of Bus Components --- p.55 / Chapter 5.3.5 --- Bus Feasibility Check --- p.56 / Chapter 5.3.6 --- Overlap Removal --- p.57 / Chapter 5.3.7 --- Floorplan Realization --- p.58 / Chapter 5.3.8 --- Simulated Annealing --- p.58 / Chapter 5.3.9 --- Soft Module Adjustment --- p.60 / Chapter 5.4 --- Experimental Results --- p.60 / Chapter 5.5 --- Summary --- p.65 / Chapter 6 --- Conclusion --- p.67 / Chapter A --- Appendix --- p.69 / Chapter A.1 --- Well-Known Algorithms --- p.69 / Chapter A.1.1 --- Kruskal's Algorithm --- p.69 / Chapter A.1.2 --- Bellman-Ford Algorithm --- p.69 / Chapter A.2 --- Figures of Resulting Floorplans --- p.71 / Chapter A.2.1 --- Data Set One --- p.71 / Chapter A.2.2 --- Data Set Two --- p.80 / Chapter A.2.3 --- Data Set Three --- p.85 / Chapter A.2.4 --- Data Set Four --- p.92 / Bibliography --- p.98

Bibliography: leaves 282-296.

In this dissertation, multi-rate array (MRA) architecture and its synthesis are proposed and developed. Using multi-coordinate systems (MCS), a unified theory for mapping algorithms from their original algorithmic specifications onto multi-rate arrays is developed. A multi-rate array is a grid of processors in which each interconnection may have its own clock rate; operations with different complexities run at their own clock rate, thus increasing the throughput and efficiency. A class of algorithms named directional affine recurrence equations (DARE) is defined. The dependence space of a DARE can be decomposed into uniform and non-uniform subspaces. When projected along the non-uniform subspace, the resultant array structure is regular. Limitations and restrictions of this approach are investigated and a procedure for mapping DARE onto MRA is developed. To generalize this approach, synthesis theory is developed with initial specification as affine direct input output (ADIO) which aims at removing redundancies from algorithms. Most ADIO specifications are the original algorithmic specifications. A multi-coordinate systems (MCS) is used to present an algorithm's dependence structures. In a MCS system, the index spaces of the variables in an algorithm are defined relative to their own coordinate systems. Most traditionally considered irregular algorithms present regular dependence structures under MCS technique. Procedures are provided for transforming algorithms from original algorithmic specifications to their regular specifications. Multi-rate schedules and multi-rate timing functions are studied. The solution for multi-rate timing functions can be formulated as linear programming problems. Procedures are provided for mapping ADIOs onto multi-rate VLSI systems. Examples are provided to illustrate the synthesis of MRAs from DAREs and ADIOs. The first major contribution of this dissertation is the development of the concrete, executable MRA architectures. The second is the introduction of MCS system and its application in the development of the theory for synthesizing MRAs from original algorithmic specifications. / Graduation date: 1995

The Weapon Target Assignment (WTA) problem is a fundamental problem arising in defense-related applications of operations research. This problem consists of optimally assigning n weapons to m targets so that the total expected survival value of the targets after all the engagements is minimum. The WTA problem can be formulated as a nonlinear integer programming problem and is known to be NP-complete. There do not exist any exact methods for the WTA problem which can solve even small size problems (for example, with 20 weapons and 20 targets). Though several heuristic methods have been proposed to solve the WTA problem, due to the absence of exact methods, no estimates are available on the quality of solutions produced by such heuristics. In this paper, we suggest linear programming, integer programming, and network flow based lower bounding methods using which we obtain several branch and bound algorithms for the WTA problem. We also propose a network flow based construction heuristic and a very large-scale neighborhood (VLSN) search algorithm. We present computational results of our algorithms which indicate that we can solve moderately large size instances (up to 80 weapons and 80 targets) of the WTA problem optimally and obtain almost optimal solutions of fairly large instances (up to 200 weapons and 200 targets) within a few seconds

Thesis (Ph. D.)--University of Chicago, Dept. of Astronomy and Astrophysics, August 1997. / Includes bibliographical references. Also available on the Internet.

M.S. / Computer Science & Engineering / Some biological aspects of neural interactions are presented and used as a basis for a computational model in the development of a new type of computer architecture. A VLSI microarchitecture is proposed that efficiently implements the neural-based computing methods. An analysis of the microarchitecture is presented to show that it is feasible using currently available VLSI technology. The performance expectations of the proposed system are analyzed and compared to conventional computer systems executing similar algorithms. The proposed system is shown to have comparatively attractive performance and cost/performance ratio characteristics. Some discussion is given on system level characteristics including initialization and learning.

M.S. / Computer Science / A general river routing algorithm is described. It is assumed that there is one layer available for routing and the terminals are on the boundaries of an arbitrarily shaped rectilinear routing region. All nets are two terminal nets. No crossover is permitted between nets. A minimum separation must be maintained between wires to prevent design rule violations. The separation and default width for all nets are obtained from a parameter file. A command line option permits the user to change the width. The algorithm assumes no grid on the routing plane. The number of corners in a given route is reduced by flipping corners.

Ces dernières années, les réseaux sont devenus une source importante d’informations dans différents domaines aussi variés que les sciences sociales, la physique ou les mathématiques. De plus, la taille de ces réseaux n’a cessé de grandir de manière conséquente. Ce constat a vu émerger de nouveaux défis, comme le besoin de mesures précises et intuitives pour caractériser et analyser ces réseaux de grandes tailles en un temps raisonnable. La première partie de cette thèse introduit une nouvelle mesure de similarité entre deux noeuds d’un réseau dirigé et pondéré : la covariance “sum-over-paths”. Celle-ci a une interprétation claire et précise : en dénombrant tous les chemins possibles deux noeuds sont considérés comme fortement corrélés s’ils apparaissent souvent sur un même chemin – de préférence court. Cette mesure dépend d’une distribution de probabilités, définie sur l’ensemble infini dénombrable des chemins dans le graphe, obtenue en minimisant l'espérance du coût total entre toutes les paires de noeuds du graphe sachant que l'entropie relative totale injectée dans le réseau est fixée à priori. Le paramètre d’entropie permet de biaiser la distribution de probabilité sur un large spectre : allant de marches aléatoires naturelles où tous les chemins sont équiprobables à des marches biaisées en faveur des plus courts chemins. Cette mesure est alors appliquée à des problèmes de classification semi-supervisée sur des réseaux de taille moyennes et comparée à l’état de l’art. La seconde partie de la thèse introduit trois nouveaux algorithmes de classification de noeuds en sein d’un large réseau dont les noeuds sont partiellement étiquetés. Ces algorithmes ont un temps de calcul linéaire en le nombre de noeuds, de classes et d’itérations, et peuvent dés lors être appliqués sur de larges réseaux. Ceux-ci ont obtenus des résultats compétitifs en comparaison à l’état de l’art sur le large réseaux de citations de brevets américains et sur huit autres jeux de données. De plus, durant la thèse, nous avons collecté un nouveau jeu de données, déjà mentionné : le réseau de citations de brevets américains. Ce jeu de données est maintenant disponible pour la communauté pour la réalisation de tests comparatifs. La partie finale de cette thèse concerne la combinaison d’un graphe de citations avec les informations présentes sur ses noeuds. De manière empirique, nous avons montré que des données basées sur des citations fournissent de meilleurs résultats de classification que des données basées sur des contenus textuels. Toujours de manière empirique, nous avons également montré que combiner les différentes sources d’informations (contenu et citations) doit être considéré lors d’une tâche de classification de textes. Par exemple, lorsqu’il s’agit de catégoriser des articles de revues, s’aider d’un graphe de citations extrait au préalable peut améliorer considérablement les performances. Par contre, dans un autre contexte, quand il s’agit de directement classer les noeuds du réseau de citations, s’aider des informations présentes sur les noeuds n’améliora pas nécessairement les performances. La théorie, les algorithmes et les applications présentés dans cette thèse fournissent des perspectives intéressantes dans différents domaines. In recent years, networks have become a major data source in various fields ranging from social sciences to mathematical and physical sciences. Moreover, the size of available networks has grow substantially as well. This has brought with it a number of new challenges, like the need for precise and intuitive measures to characterize and analyze large scale networks in a reasonable time. The first part of this thesis introduces a novel measure between two nodes of a weighted directed graph: The sum-over-paths covariance. It has a clear and intuitive interpretation: two nodes are considered as highly correlated if they often co-occur on the same -- preferably short -- paths. This measure depends on a probability distribution over the (usually infinite) countable set of paths through the graph which is obtained by minimizing the total expected cost between all pairs of nodes while fixing the total relative entropy spread in the graph. The entropy parameter allows to bias the probability distribution over a wide spectrum: going from natural random walks (where all paths are equiprobable) to walks biased towards shortest-paths. This measure is then applied to semi-supervised classification problems on medium-size networks and compared to state-of-the-art techniques. The second part introduces three novel algorithms for within-network classification in large-scale networks, i.e., classification of nodes in partially labeled graphs. The algorithms have a linear computing time in the number of edges, classes and steps and hence can be applied to large scale networks. They obtained competitive results in comparison to state-of-the-art technics on the large scale U.S.~patents citation network and on eight other data sets. Furthermore, during the thesis, we collected a novel benchmark data set: the U.S.~patents citation network. This data set is now available to the community for benchmarks purposes. The final part of the thesis concerns the combination of a citation graph with information on its nodes. We show that citation-based data provide better results for classification than content-based data. We also show empirically that combining both sources of information (content-based and citation-based) should be considered when facing a text categorization problem. For instance, while classifying journal papers, considering to extract an external citation graph may considerably boost the performance. However, in another context, when we have to directly classify the network citation nodes, then the help of features on nodes will not improve the results. The theory, algorithms and applications presented in this thesis provide interesting perspectives in various fields.

In solving noise-free and noisy optimization problems, candidate initialization and sampling play a key role, but are not deeply investigated. It is of interest to know if the entire search space has the same quality for candidate-solutions during solving different type of optimization problems. In this thesis, a comprehensive investigation is conducted in order to clear those doubts, and to examine the effects of variant sampling methods on solving challenging optimization problems, such as large-scale, noisy, and multi-modal problems. As a result, the search space is segmented by using seven segmentation schemes, namely: Center-Point, Center-Based, Modula-Opposite, Quasi-Opposite, Quasi-Reflection, Supper- Opposite, and Opposite-Random. The introduced schemes are studied using Monte-Carlo simulation, on various types of noise-free optimization problems, and ultimately ranked based on their performance in terms of probability of closeness, average distance to unknown solution, number of solutions found, and diversity. Based on the results of the experiments, high-ranked schemes are selected and utilized on well-known metaheuristic algorithms, as case studies. Two categories of case studies are targeted; one for a singlesolution- based metaheuristic (S-metaheuristic) and another one for a population based metaheuristic (P-metaheuristic). A high-ranked single-solution-based scheme is utilized to accelerate Simulated Annealing (SA) algorithm, as a noise-free S-metaheuristic case study. Similarly, for noise-free P-metaheuristic case study, an effective population-based algorithm, Differential Evolution (DE), has been utilized. The experiments confirm that the new algorithms outperform the parent algorithm (DE) on large-scale problems. In the same direction, with regards to solving noisy problems more efficiently, a Shaking-based sampling method is introduced, in which the original noise is tackled by adding an additional noise into the search process. As a case study, the Shaking-based sampling is utilized on the DE algorithm, from which two variant algorithms have been developed and showed impressive performance in comparison to the classical DE, in tackling noisy largescale problems. This thesis has created an opportunity for a comprehensive investigation on search space segmentation schemes and proposed new sampling methods. The current study has provided a guide to use appropriate sampling schemes for a given types of problems such as noisy, large-scale and multi-modal optimization problems. Furthermore, this thesis questions the effectiveness of uniform-random sampling method, which is widely used in of S-Metaheuristic and P-Metaheuristic algorithms. / UOIT