As digital systems continue to grow in complexity, the design of conventional synchronous systems is facing unprecedented challenges. The number of transistors on individual chips is already in the multi-billion range, and a greatly increasing number of components are being integrated onto a single chip. As a consequence, modern digital designs are under strong time-to-market pressure, and there is a critical need for composable design approaches for large complex systems. In the past two decades, networks-on-chip (NoC’s) have been a highly active research area. In a NoC-based system, functional blocks are first designed individually and may run at different clock rates. These modules are then connected through a structured network for on-chip global communication. However, due to the rigidity of centrally-clocked NoC’s, there have been bottlenecks of system scalability, energy and performance, which cannot be easily solved with synchronous approaches. As a result, there has been significant recent interest in combing the notion of asynchrony with NoC designs. Since the NoC approach inherently separates the communication infrastructure, and its timing, from computational elements, it is a natural match for an asynchronous paradigm. Asynchronous NoC’s, therefore, enable a modular and extensible system composition for an ‘object-orient’ design style. The thesis aims to significantly advance the state-of-art and viability of asynchronous and globally-asynchronous locally-synchronous (GALS) networks-on-chip, to enable high-performance and low-energy systems. The proposed asynchronous NoC’s are nearly entirely based on standard cells, which eases their integration into industrial design flows. The contributions are instantiated in three different directions. First, practical acceleration techniques are proposed for optimizing the system latency, in order to break through the latency bottleneck in the memory interfaces of many on-chip parallel processors. Novel asynchronous network protocols are proposed, along with concrete NoC designs. A new concept, called ‘monitoring network’, is introduced. Monitoring networks are lightweight shadow networks used for fast-forwarding anticipated traffic information, ahead of the actual packet traffic. The routers are therefore allowed to initiate and perform arbitration and channel allocation in advance. The technique is successfully applied to two topologies which belong to two different categories – a variant mesh-of-trees (MoT) structure and a 2D-mesh topology. Considerable and stable latency improvements are observed across a wide range of traffic patterns, along with moderate throughput gains. Second, for the first time, a high-performance and low-power asynchronous NoC router is compared directly to a leading commercial synchronous counterpart in an advanced industrial technology. The asynchronous router design shows significant performance improvements, as well as area and power savings. The proposed asynchronous router integrates several advanced techniques, including a low-latency circular FIFO for buffer design, and a novel end-to-end credit-based virtual channel (VC) flow control. In addition, a semi-automated design flow is created, which uses portions of a standard synchronous tool flow. Finally, a high-performance multi-resource asynchronous arbiter design is developed. This small but important component can be directly used in existing asynchronous NoC’s for performance optimization. In addition, this standalone design promises use in opening up new NoC directions, as well as for general use in parallel systems. In the proposed arbiter design, the allocation of a resource to a client is divided into several steps. Multiple successive client-resource pairs can be selected rapidly in pipelined sequence, and the completion of the assignments can overlap in parallel. In sum, the thesis provides a set of advanced design solutions for performance optimization of asynchronous and GALS networks-on-chip. These solutions are at different levels, from network protocols, down to router- and component-level optimizations, which can be directly applied to existing basic asynchronous NoC designs to provide a leap in performance improvement.

Fung, Wai Shing. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 70-76). / Abstract also in Chinese. / Abstract --- p.i / Acknowledgement --- p.iii / Chapter 1 --- Overview --- p.1 / Chapter 1.1 --- Background --- p.1 / Chapter 1.1.1 --- Network Design --- p.1 / Chapter 1.1.2 --- Degree Bounded Network Design --- p.3 / Chapter 1.1.3 --- Degree Bounded Vertex Connectivity Network Design --- p.6 / Chapter 1.2 --- Our Results --- p.7 / Chapter 1.2.1 --- Problem Definition --- p.8 / Chapter 1.2.2 --- Main Result --- p.8 / Chapter 1.2.3 --- Organization of This Thesis --- p.9 / Chapter 1.3 --- Algorithm Outline --- p.10 / Chapter 1.3.1 --- Christofides' Algorithm for TSP --- p.10 / Chapter 1.3.2 --- Extending Christofides´ة Algorithm to K > 2 --- p.12 / Chapter 1.3.3 --- Bienstock et al´ةs Splitting-Off Theorem --- p.13 / Chapter 2 --- Basics --- p.18 / Chapter 2.1 --- Notations and Terminology --- p.18 / Chapter 2.2 --- .Menger's Theorem --- p.20 / Chapter 2.3 --- Submodular Functions --- p.21 / Chapter 2.4 --- Use of Submodularity in Proofs of Splitting-Off Theorems --- p.22 / Chapter 2.5 --- Splitting-Off Concerning Edge Connectivity --- p.27 / Chapter 2.6 --- Splitting-Off Concerning Vertex Connectivity --- p.30 / Chapter 2.7 --- Vertex Connectivity Network Design --- p.32 / Chapter 2.7.1 --- Rooted Connectivity --- p.33 / Chapter 2.7.2 --- Global Connectivity --- p.35 / Chapter 2.7.3 --- Generalized Steiner Network --- p.36 / Chapter 2.8 --- Network Design with Metric Cost --- p.37 / Chapter 2.8.1 --- Minimum Cost K-Vertex-Connected Subgraph --- p.38 / Chapter 2.8.2 --- Degree Bounded Minimum Spanning Tree --- p.40 / Chapter 3 --- Minimum Degree K-Vertex-Connected Subgraph --- p.42 / Chapter 3.1 --- Preliminary --- p.44 / Chapter 3.1.1 --- Tight Sets --- p.44 / Chapter 3.1.2 --- (xxi)-Critical Sets --- p.46 / Chapter 3.2 --- Splitting-Off with Parallel Edges --- p.47 / Chapter 3.2.1 --- When Does Replacement Fail? --- p.48 / Chapter 3.2.2 --- Deriving a Special Structure --- p.50 / Chapter 3.2.3 --- Such Structure Is Impossible --- p.50 / Chapter 3.3 --- Splitting-Off with Redundant Edges --- p.50 / Chapter 3.3.1 --- Proof Outline --- p.51 / Chapter 3.3.2 --- When Does Splitting-Off Fail? --- p.54 / Chapter 3.3.3 --- Admissible Pairs Exists If Two Redundant Edges Are Present --- p.57 / Chapter 3.3.4 --- Proof of Property(T*) --- p.58 / Chapter 3.3.5 --- Existence of Jointly Admissible Pairs --- p.62 / Chapter 3.4 --- Main Algorithm --- p.66 / Chapter 4 --- Concluding Remarks --- p.69 / Bibliography --- p.70

Yung, Chun Kong. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2009. / Includes bibliographical references (leaves 121-129). / Abstracts in English and Chinese. / Chapter 1 --- Overview --- p.2 / Chapter 2 --- Background --- p.7 / Chapter 2.1 --- Graphs and Edge-connectivitv --- p.7 / Chapter 2.1.1 --- Subgraphs --- p.9 / Chapter 2.1.2 --- Cut and Edge-Connectivitv --- p.10 / Chapter 2.1.3 --- Menger's Theorem --- p.12 / Chapter 2.2 --- Edge Splitting-off --- p.13 / Chapter 2.2.1 --- The Basics --- p.15 / Chapter 2.2.1.1 --- Supermodular and Submodular Set Functions --- p.16 / Chapter 2.2.1.2 --- Set Functions regarding Edge-Connectivity --- p.17 / Chapter 2.2.1.3 --- Dangerous and Tight Sets --- p.18 / Chapter 2.2.2 --- Proof of Mader's Theorem --- p.20 / Chapter 2.2.3 --- Global Arc-Connectivity Setting --- p.23 / Chapter 2.2.3.1 --- Local Arc-Connectivity Setting --- p.25 / Chapter 2.2.4 --- Incorporating Additional Properties --- p.26 / Chapter 2.2.4.1 --- Non-Admissibility Graph Method --- p.27 / Chapter 2.3 --- Edge-Connectivity Problems --- p.29 / Chapter 2.3.1 --- Degree Bounded Network Design Problems --- p.30 / Chapter 2.3.1.1 --- Metric Cost Assumption --- p.31 / Chapter 2.3.2 --- Edge-Connectivitv Augmentation Problems --- p.33 / Chapter 2.3.2.1 --- Prank's Framework --- p.34 / Chapter 2.3.2.2 --- Constrained Edge-Connectivity Augmentation Problems --- p.36 / Chapter 2.3.3 --- Edge Splitting-off Problems --- p.39 / Chapter 2.4 --- Edge Splitting-off Algorithms --- p.40 / Chapter 2.4.1 --- Fastest Algorithms --- p.41 / Chapter 2.4.2 --- An Intuitive Approach --- p.42 / Chapter 2.4.3 --- Global Connectivity Settings --- p.42 / Chapter 2.4.3.1 --- Legal Ordering --- p.43 / Chapter 2.4.3.2 --- Edmonds' Arborescences --- p.44 / Chapter 2.4.4 --- Local Edge-Connectivity Setting --- p.45 / Chapter 3 --- Degree Bounded Network Design Problem with Metric Cost --- p.47 / Chapter 3.1 --- Christofides'-like Algorithm --- p.49 / Chapter 3.2 --- Simplicity-Preserving Edge Splitting-Off --- p.50 / Chapter 3.2.1 --- Proof of Theorem 3.3 --- p.51 / Chapter 3.3 --- Approximation Algorithms for Network Design Problems --- p.56 / Chapter 3.3.1 --- Removing Redundant Edges --- p.57 / Chapter 3.3.2 --- Perfect Matching --- p.58 / Chapter 3.3.3 --- Edge Splitting-Off Restoring Simplicity --- p.59 / Chapter 3.4 --- Results in Different Settings --- p.60 / Chapter 3.4.1 --- Global Edge-Connectivity --- p.61 / Chapter 3.4.2 --- Local Edge-Connectivity --- p.62 / Chapter 4 --- Constrained Edge Splitting-off --- p.64 / Chapter 4.1 --- Preliminaries --- p.66 / Chapter 4.2 --- General Constrained Edge Splitting-off Lemma --- p.68 / Chapter 4.3 --- Structural Properties of Non-Admissible Pairs --- p.69 / Chapter 4.3.1 --- Some Useful Lemmas --- p.70 / Chapter 4.3.2 --- An Upper Bound on \Dp\ --- p.71 / Chapter 4.3.3 --- An Inductive Argument --- p.73 / Chapter 4.4 --- Non-Admissibility Graph and Constraint Graph --- p.75 / Chapter 4.4.1 --- Vertex Set Partition Constraint --- p.76 / Chapter 4.4.2 --- Graph Simplicity Constraint --- p.77 / Chapter 4.4.3 --- Simultaneous Graph Constraint --- p.78 / Chapter 4.4.4 --- Tight Sufficient Conditions --- p.79 / Chapter 4.5 --- Global Arc-Connectivity Setting --- p.79 / Chapter 4.5.1 --- Proof of Lemma 4.15 --- p.81 / Chapter 5 --- Constrained Edge-Connectivity Augmentation Problem --- p.83 / Chapter 5.1 --- Preliminaries --- p.84 / Chapter 5.2 --- Additive Approximation Algorithms --- p.87 / Chapter 5.2.1 --- Edge-Connectivitv Augmentation Preserving Vertex Set Partition --- p.87 / Chapter 5.2.2 --- Edge-Connectivity Augmentation Preserving Simplicity --- p.91 / Chapter 5.2.3 --- Simultaneous-Graph Edge-Connectivity Augmentation --- p.93 / Chapter 5.3 --- Global Arc-Connectivity Setting --- p.95 / Chapter 5.3.1 --- Edge-Connectivity Augmentation Preserving Vertex Set Partition --- p.95 / Chapter 5.3.2 --- Edge-Connectivity Augmentation Preserving Simplicity --- p.97 / Chapter 5.3.3 --- Simultaneous Edge-Connectivity Augmentation --- p.98 / Chapter 6 --- Efficient Edge Splitting-off Algorithm --- p.100 / Chapter 6.l --- Preliminaries --- p.102 / Chapter 6.1.1 --- Efficient Tools for Edge-Connectivity Problems --- p.103 / Chapter 6.1.2 --- An Alternative Proof of Mader's Theorem --- p.104 / Chapter 6.2 --- Framework for Complete Edge Splitting-off --- p.105 / Chapter 6.2.1 --- Proof of Lemma 6.5 --- p.106 / Chapter 6.3 --- Efficient Splitting-off Attempt --- p.108 / Chapter 6.3.1 --- Indicator Vertex --- p.109 / Chapter 6.3.2 --- Splitting-off to Capacity --- p.112 / Chapter 6.4 --- Randomized and Parallelized Edge Splitting-off Algorithm --- p.113 / Chapter 6.5 --- Deterministic Edge Splitting-off Algorithm --- p.114 / Chapter 6.6 --- Algorithms in Other Settings --- p.115 / Chapter 6.6.1 --- Edge Splitting-off in Network Design Problems --- p.115 / Chapter 6.6.2 --- Constrained Edge Splitting-off --- p.116 / Chapter 7 --- Concluding Remarks --- p.119 / Bibliography --- p.121

No description available.

Not available / text

No description available.

The price of anarchy, a concept introduced by Koutsoupias and Papadimitriou [9], is the main topic of this thesis. It is a measure of the loss of efficiency that occurs when there is no central control over a system consisting of many "selfish" agents. We will be particularly interested in this in the context of network games, which can be used to model congestion in traffic and communication networks. / After an introduction of the relevant concepts and review of related work, we proceed with the new results of this thesis. We provide a new upper bound for the price of anarchy in the case of atomic unsplittable agents with polynomial cost functions, and demonstrate that it is tight by an explicit construction. We then introduce a new model for network routing that introduces priorities; users with a higher priority on a link will be able to traverse the link more quickly. Our model is fairly general, and allows various different priority schemes for modelling different situations. One particularly interesting version, which we have dubbed the timestamp game, assigns priorities according to the order of arrival at the start of the link. / We derive tight upper bounds for the price of anarchy in our model in the case of polynomial cost functions and nonatomic agents. We also obtain tight results in the unsplittable case with linear cost functions, and an upper bound with polynomial cost functions. / While we concentrate on network games, most of the results carry through to the more general class of congestion games, which we also discuss.

Thesis (M.S.)--University of Hawaii at Manoa, 2006. / Includes bibliographical references (leaves 61-63). / ix, 63 leaves, bound ill. 29 cm

This thesis presents the development and implementation of a token bus protocol for a Power Line Local Area Network (PLLAN) which utilizes intra-building power distribution circuit as the physical transmission medium. This medium provides a low cost means for data communications with a high degree of portability. Due to the characteristics of the power line and the prototype modem, the network would be easily saturated with data and would have a high collision probabilities. The IEEE 802.4 token bus standard is modified to fit the PLLAN and to bring its performance up. A comparative performance of the original protocol and the modified version shows that the latter provides an improvement in network throughput of up to 15 percent and a reduction in the network join-ring delay of up to 20 percent for a wide workload range. The performance figures of the modified version in a power line network of three SUN 3/50 workstations¹ transmitting at 9.6 kilo-bit per second is also presented and analyzed. ¹Sun workstation is a trademark of Sun Microsystems. / Science, Faculty of / Computer Science, Department of / Graduate

by Chan Tsan Jim. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2003. / Includes bibliographical references (leaves 68-71). / Abstracts in English and Chinese. / Chapter Chapter 1 --- Introduction --- p.1 / Chapter 1.1 --- Introduction --- p.1 / Chapter 1.2 --- Background --- p.2 / Chapter 1.2.1 --- Introduction --- p.2 / Chapter 1.2.2 --- Wavelength Division Multiplexing --- p.3 / Chapter 1.2.3 --- Arrayed Waveguide Grating --- p.5 / Chapter 1.2.4 --- Passive Optical Networks --- p.7 / Chapter 1.3 --- Outline of the thesis --- p.10 / Chapter Chapter 2 --- Review of Protection and Restoration Schemes --- p.12 / Chapter 2.1 --- Introduction --- p.12 / Chapter 2.2 --- Protection Schemes --- p.14 / Chapter 2.2.1 --- Path Protection --- p.14 / Chapter 2.2.2 --- Link Protection --- p.16 / Chapter 2.3 --- Restoration Schemes --- p.17 / Chapter 2.3.1 --- Path Restoration --- p.17 / Chapter 2.3.2 --- Link Restoration --- p.18 / Chapter 2.4 --- Protection and Restoration Schemes in PON --- p.18 / Chapter 2.4.1 --- Protection Schemes in G.983.1 --- p.18 / Chapter 2.4.2 --- Other Proposed Schemes --- p.21 / Chapter Chapter 3 --- Design of WDM PON Network Architecture --- p.26 / Chapter 3.1 --- Introduction --- p.26 / Chapter 3.2 --- The Group Protection Architecture (GPA) --- p.27 / Chapter 3.2.1 --- Network Design --- p.27 / Chapter 3.2.2 --- Protection Mechanism --- p.28 / Chapter 3.2.3 --- Wavelength Assignments --- p.30 / Chapter 3.2.4 --- Power Budget Calculation --- p.32 / Chapter 3.2.5 --- Crosstalk Analysis --- p.33 / Chapter 3.2.6 --- Discussion --- p.35 / Chapter 3.3 --- The Enhanced Group Protection Architecture (EGPA) --- p.36 / Chapter 3.3.1 --- Introduction --- p.36 / Chapter 3.3.2 --- Network Design --- p.37 / Chapter 3.3.3 --- Protection Mechanism --- p.38 / Chapter 3.3.4 --- Wavelength Assignments --- p.39 / Chapter 3.3.5 --- Power Budget Calculation --- p.40 / Chapter 3.3.6 --- Crosstalk Analysis --- p.41 / Chapter 3.3.7 --- Discussion --- p.42 / Chapter 3.4 --- The Hybrid Ring Architecture (HR) --- p.42 / Chapter 3.4.1 --- Introduction --- p.42 / Chapter 3.4.2 --- Network Design --- p.43 / Chapter 3.4.3 --- Protection Mechanism --- p.44 / Chapter 3.4.4 --- Wavelength Assignments --- p.45 / Chapter 3.4.5 --- Power Budget Calculation --- p.46 / Chapter 3.4.6 --- Crosstalk Analysis --- p.47 / Chapter 3.4.7 --- Discussion --- p.47 / Chapter 3.5 --- Comparison of the three schemes --- p.48 / Chapter 3.6 --- Summary of the three schemes --- p.50 / Chapter Chapter 4 --- Experimental Evaluation --- p.51 / Chapter 4.1 --- Introduction --- p.51 / Chapter 4.2 --- Experimental Setup --- p.51 / Chapter 4.2.1 --- The GPA Scheme --- p.51 / Chapter 4.2.2 --- The EGPA Scheme --- p.53 / Chapter 4.2.3 --- The HR Scheme --- p.54 / Chapter 4.3 --- Experimental Result --- p.55 / Chapter 4.3.1 --- Optical Spectrum --- p.55 / Chapter 4.3.2 --- Transmission Performance --- p.58 / Chapter 4.3.3 --- Switching/Restoration Time --- p.61 / Chapter 4.3.4 --- Crosstalk Penalty --- p.63 / Chapter 4.4 --- Conclusion --- p.64 / Chapter Chapter 5 --- Conclusion and Future Works --- p.65 / Chapter 5.1 --- Introduction --- p.65 / Chapter 5.2 --- Conclusion --- p.65 / Chapter 5.3 --- Future Works --- p.66 / References --- p.67