- U of Warwick, CS 185(dir)
- Gibbons, A.M. ``A Tutorial Introduction to Distributed Memory Models of Parallel Computation.'' Technical Report, UWARWICK//CS-RR-185, University of Warwick, Department of Computer Science. November 1992.
- ABSTRACT
- This is an introduction to distributed memory models of parallel computation. Communication networks that have been advocated for general purposes are described and the problem of parallel routing within these networks is addressed through the permutation routing paradigm. A number of basic techniques are briefly introduced for efficient implementation of P-RAM algorithms on distributed memory models of parallel computation. These include techniques which are dependent on network topology or algorithmic structure, such as graph embedding and the method of compress and iterate as well as techniques with less specific application such as the employment of hashing and the use of parallel slackness to hide network latency.
- BIB-VERSION
- CS-TR-v2.0
- ENTRY
- January 20, 1995
- LANGUAGE
- English
- NOTES
- This report has been published, and is not available online; a citation of the published version is available in BiBTeX format (citation.bib) by anonymous FTP from ftp://ftp.dcs.warwick.ac.uk/pub/reports/rr/185/
- U of Alberta CS TR92-01(dir) TR92-01.abstract(symlink)
- Zhiyong Liu and Xiaobo Li Routing Linear Complement Permutations on Hypercubes 1992 TR 92-01 hypercube, linear complement permutations, routing algorithms, conflict, complexity
- U of Colorado, Boulder CS ReplSvrLoc.ps.Z(109K) ReplSvrLoc.txt.Z(19K)
- James D. Guyton, Michael F. Schwartz. ``Locating Nearby Copies of Replicated Internet Servers.'' Technical Report CU-CS-762-95, Department of Computer Science, University of Colorado, Boulder, Colorado,
Keywords: NTP discovery, resource discovery, RD, server location, anycast, expanding ring broadcast, multicast triangulation, application layer, network probing, proactive gathering, server location techniques, reactive gathering, in routing layer, routing table polling, route probing, hop count probing
Submitted for publication
Abstract: "In this paper we consider the problem of choosing among a collection of replicated servers, focusing on the question of how to make choices that segregate client/server traffic according to network topology. We explore the cost and effectiveness of a variety of approaches, ranging from those requiring routing layer support (e.g., anycast) to those that build location databases using application-level probe tools like traceroute. We uncover a number of tradeoffs between effectiveness, network cost, ease of deployment, and portability across different types of networks. We performed our experiments using a simulation parameterized by a topology collected from 7 survey sites across the United States, exploring a global collection of Network Time Protocol servers."
- U of Massachusetts Amherst, CoInS documents(dir)
- A Dual Optimization Approach for Distributed Minimum Delay Routing With Kyoo Jeong Lee, Don Towsley and Myungwhan Choi UM-CS-1987-113* Distributed Optimization Algorithms for Quasi-Static Threshold Load Comments: This report is only available in hardcopy form. Kyoo Jeong Lee and Don Towsley 10/27/87, 10/27/87 Comments: This report is only available in hardcopy form. UM-CS-1988-016* Retrieving Documents by Plausible Inference W.B. Croft, T.J. Lucia and P.R. Cohen 04/30/88, 04/30/88 Comments: This report is only available in hardcopy form.
- U of California Berkeley, ERL erl-90-27(dir)
- Jackson, Michael A.B.; Srinivasan, Arvind; Kuh, Ernest S. ``A Novel Approach to IC Performance Optimization by Clock Routing.'' UCB//ERL-90-27, April, 1990. 34 pages.
- ABSTRACT
- In today's highly competitive IC marketplace, company survival necessitates product differentiability. Product differentiability may be engendered in many ways, several of which include: increased performance (e.g. lower power, faster timing, etc...), lower cost, more features, or faster time to market. Thus, the motivation for design techniques that enhance chip timing performance are of fundamental importance to the IC community.
The clock is the essence of a synchronous digital system. Physically, the clock is distributed from an external pad to all similarly clocked synchronizing elements through a distribution network that encompasses combinational logic and interconnects. It serves to unify the physical and temporal design abstractions by determining the precise instants in time at which the digital machine changes state. Because the clock is important, optimization of the clock signal can have a significant impact on the chip's cycle time, especially in high-performance designs. Non-optimal clock behavior is caused by two phenomena: the routing to the chip's synchronizing elements, and the asymmetric behavior of the clock distribution logic.
Previous work in clock optimization has been contributed by several authors. H-trees have been recognized for years as a technique to help reduce the skew in synchronous systems [FK82] [KGE82] [DFW84] [BWM86]. For regular structures such as systolic arrays the H-tree works well to reduce skew because the synchronizing elements are distributed in a uniform pattern throughout the chip. However, for general design styles, nonuniform distributions of clock pins are common and the H-tree becomes ineffective as a technique for clock routing. The large size of the clock net has led some researchers [DFW84] [Mij87] to perform buffer optimization within the clock distribution tree. [BWM86] have provided an analysis of the clock tree that considers the transmission line properties of the interconnects. [BBB +89] have presented an approach for ASIC clock distribution that integrates buffer optimization into place and route algorithms. However, in all previous work the routing of the clock net is performed using ordinary global routing tools based on minimum spanning or approximate minimum Steiner tree net models and with detailed routers that have little understanding of clock routing problems. This causes non-optimal clock behavior and as region size or the number of pins in the clock net increases, the detrimental behavior is exacerbated. In this paper, we focus on routing techniques for optimizing clock signals in VLSI circuits. We demonstrate the superiority of our algorithm over standard routing techniques for widely varying region size, clock pin distributions, numbers of clock pins and technology feature size.
In section two the preliminaries necessary for understanding the paper are presented. Following this, in section three the problem is defined. Section four illustrates the algorithm for clock routing and section five discusses theoretical results. Next, in section six the experimental results are presented, and in section seven possible avenues for future work and conclusions regarding the approach are discussed.
- ENTRY
- Sep 14, 1994
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-034}.tif)
- U of California Berkeley, CS csd-88-487(dir)
- Tonogai, Dale. ``AI in Operating Systems: An Expert Scheduler.'' UCB//CSD-88-487, 32 pages.
- ABSTRACT
- The allocation of resources in operating systems is currently based on ad hoc heuristics and algorithms. Some well-known heuristics have been developed in such areas as process scheduling, memory management and network routing. The possibility that better decisions could be made by an Intelligent Agent employing expert system techniques is investigated in this report. The ability to learn from experience and to deal with uncertainty are two characteristics of expert systems that would be essential aspects of such an Intelligent Agent.
As multiple processor systems become more widely available, applications involving multiple concurrent processes will increase in number and importance. This increased interdependency among processes poses interesting problems in the area of processor scheduling. How should the processes be scheduled to achieve some optimal level of performance? A scheduler based on an expert system may prove to be a viable alternative to those that have been proposed and (in some cases) implemented so far.
This report describes the implementation of a learning mechanism that attempts to handle the problem of processor scheduling in such a multiprocessor environment. In effect, the Intelligent Agent tries to "learn" its own set of heuristics for optimally scheduling a set of co-operating processes. By simulating a relatively simple multiprocessor system we examine the merits of such an approach.
- ENTRY
- July 26, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-032}.tif)
- Simon Fraser U, SCS CMPT94-11.ps.Z(107K)
- TechReport{U-SFraser-CMPT-TR:1994-11, number = "TR 94-11", author = "Jave O. Kane and Joseph G. Peters", title = "Line Broadcasting in Cycles", month = dec, year = "1994", org = "SFU-CMPT", school = SFU_CS_School, pages = "20", keywords = "broadcasting, embedding, circuit-switched routing", amos = "94A05, 68M10", abstract = "Broadcasting is the process of transmitting information from an originating node (processor) in a network to all other nodes in the network. A local broadcast scheme only allows a node to send information along single communication links to adjacent nodes, while a line broadcast scheme allows nodes to use paths of several communication links to call distant nodes. The minimum time possible for broadcasting in a network of n nodes when no node is involved in more than one communication at any given time is log n phases. Local broadcasting is not sufficient, in general, for broadcasting to be completed in minimum-time; line broadcasting is always sufficient. An optimal line broadcast is a minimum-time broadcast that uses the smallest possible total number of communication links. In this paper, we give a complete characterization of optimal line broadcasting in cycles, and we develop efficient methods for constructing optimal line broadcast schemes.", URL = "ftp://ftp.fas.sfu.ca/pub/cs/techreports/1994/CMPT94-11.ps.Z", }
- INRIA (Natl Inst Res Comp & Ctl Sci, France) RR-2443.ps.gz(98K)
- RR-2443.ps.gz KOOLE (Ger) : n the pathwise optimal Bernoulli routing policy for homogeneous parallel servers
- U of California Berkeley, CS csd-84-202(dir)
- Raghavan, Prabhakar; Thompson, Clark D. ``Randomized Routing in Gate-Arrays.'' UCB//CSD-84-202, September 1984. 20 pages.
- ABSTRACT
- A stochastic model for analyzing the performance of randomized algorithms for routing gate-arrays is presented; our model is based on an empirical observation known as Rent's Rule. Using the model, we analyze the space requirement of a wiring technique that only uses one-bend routes. We show how the tech nique can be extended to a case where several wiring layers are available, wiht near-optimal saving in area. As a by-product, we obtain a random procedure for converting a two-layer gate-array routing to a many-layer routing while reducing area efficiently. Within our model, we also show that the one-bend strategy is sub- optimal in terms of space requirement. However, we also show that the optimal strategy is not significantly superior to the random one-bend strategy.
- ENTRY
- September 21, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-020}.tif)
- U of California Berkeley, CS csd-84-185(dir)
- Ramamoorthy, C. V.; Nishiguchi, O.; Tsai, W.-T. ``Simulation of Hierarchical Routing Algorithms.'' UCB//CSD-84-185, 16 pages.
- ABSTRACT
- This document describes two routing simulators for computer communication for communication networks. One is to simulate the new Arpanet routing algorithm [MCQ 80] and its extension to hierarchical networks [TSA 82, RAM 83], and the other one for the original Arpanet routing algorithm [MCQ 74] and its extension to hierarchical networks [MCQ 74, KAM 76, HER 82]. The novel features of the simulators are that they are highly parametrized so that they could be used for a variety of purposes. Specifically, the input network could be arbitrary clustering structures, the reliability of links of networks could be arbitrarily chosen, the delay along each link could be arbitrarily predetermined according to the real network environments, and the patterns and flow rates of input data streams could be arbitrarily chosen. This report is intended to be used as a manual for using the simulators, thus many details of the algorithms will not be presented for the sake of brevity. The detailed algorithms could be found in [MCQ 7, MCQ 80, RAM 83].
- ENTRY
- September 29, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-016}.tif)
- U of California Berkeley, CS csd-83-154(dir)
- Ousterhout, John K.; Hamachi, Gordon T.; Mayo, Robert Nelson; Scott, Walter Stewart; Taylor, George S. ``A Collection of Papers on Magic.'' UCB//CSD-83-154, December 2, 1983. 104 pages.
- ABSTRACT
- Magic is a "smart" layout system for integrated circuits. It incorporates expertise about design rules and connectivity directly into the layout system in order to implement powerful new operations, including: a continuous design-rule checker that operates in background to maintain an up-to-date picture of violations; an operation called plowing that permits interactive stretching and compaction; and routing tools that can work under and around existing connections in the channels. Magic uses a new data structure called corner stitching to achieve an efficient implementation of these operations.
- ENTRY
- July 3, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-104}.tif)
- U of California Berkeley, CS csd-83-137(dir)
- Fujimoto, Richard M. ``VLSI Communication Components for Multicomputer Networks.'' UCB//CSD-83-137, 234 pages.
- ABSTRACT
- Advances in microporecessor technology will soon make general purpose computing systems composed of thousands of VLSI processors economically feasible. A high-performance communication system to interconnect these processors is of crucial importance to exploit the parallelism inherent in application such as circuit simulation and signal processing. This thesis discusses issues in the design of universal VLSI communication components to be used as the building blocks for constructing robust, high-bandwidth, point-to-point networks. The component provide enough flexibility to serve a wide variety of multicomputer configurations and applications. They feature special purpose hardware to implement communication functions traditionally implemented with network software.
A communication network constructed from the proposed components is modeled as a set of nodes (components) connected by bidirectional communication links. Because of technological constraints, the total I/O bandwidth of each node is limited to some fixed value, and assumed to be equally divided among the attached links. Increasing the number of links per component leads to a reduction in the average number of hops between nodes, but at the cost of reduced link bandwidth. This "hop count/ link bandwidth" tradeoff is examined in great detail through M/M/1 queueing models and simulations using traffic loads generated by parallel application programs. These results indicate that a small number of links should be used. It is also found that a significant improvement in performance is obtained if a component is allowed to immediately begin forwarding a message when the selected output link becomes idle, regardless of whether or not the end of the message has arrived. Finally, mechanisms which efficiently transmit a single message to multiple destinations are seen to have a significant impact on performance in programs relying on global information.
The complexity of the circuitry required to implement a communication component is examined. Schemes for providing hardware support for communication functions--routing, buffer management, and flow control--are presented. Estimates of the number of buffers and the degree of multiplexing on each communication link are determined. The amount of circuitry to implement a communication component is computed, and it is seen that the proposed communication component could be complemented with technology available today. Design recommendations for the implementation of such a component are made.
- ENTRY
- July 9, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-234}.tif)
- U of California Berkeley, CS csd-88-412(dir)
- Srini, Vason P.; Tam, Jerric V.; Nguyen, Tam M.; Holmer, Bruce K.; Patt, Yale N.; Despain, Alvin M. ``Design and Implementation of A CMOS Chip for Prolog.'' UCB//CSD-88-412, 132 pages.
- ABSTRACT
- We have designed and fabricated a high performance VLSI chip for executing Prolog programs using a 1.4 micron CMOS technology with two layers of metal. This chip implements a tagged architecture with hardware support for five stacks.The 32-bit data path of the chip contains a fast ALU, 64 registers in four groups, five counters, and six non-master/slave registers. The control is microprogrammed and uses a 512 X 160 bit ROM with four pages for fast microbranching. The chip operates at a cycle time of 100 ns (worst case) and has a size of 10 mm X 9 mm. A semicustom design methodology employing Mentor and NCR tools has been used in design. The challenges involved in the design, verification, routing, and fabrication of the chip are described.
- ENTRY
- October 11, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-132}.tif)
- U of California Berkeley, CS csd-88-393(dir)
- Mayo, Robert Nelson. ``Mocha Chip: A Graphical Programming System for IC Module Assembly.'' UCB//CSD-88-393, 1987. 180 pages.
- ABSTRACT
- Mocha Chip is a system for designing module generators. There are two unique aspects to this system: diagrams are used to represent the the structure of a module generator, and assembly primitives ensure that the generated layout obeys geometrical design rules and is properly connected.
Module generators are created using hierarchical diagrams rather than programs. The idea is to draw diagrams describing the topology of a class of modules, and to parameterize the diagrams to indicate how the individual modules differ. Parameterization is done using Lisp and special built-in cells that provide graphical representations of iteration and conditional selection. The diagrams may be considered to be a graphical representation of iteration and conditional selection. The diagrams may be considered to be a graphical programming language tailored to IC design. Diagrams can invoke either other diagrams or cells of mask geometry drawn by the user.
Describing module generators with graphics rather than text adds flexibility to the module generator. Textual languages, such as programming languages, tend to obscure the geometrical relationships. Mocha Chip separates out the module structure and represents it graphically, resulting in module generators that are easier to design and modify. Openness and ease of modification are important since users need to tailor module generators to produce specialized modules.
Layout for a module is produced using two pairwise assembly operators that take pieces of layout and combine them to form a larger pieces. The tile-packing operator aligns user-specified rectangles. The river-route-space operator uses two phases. The routing phase connects ports that do not line up exactly, and\ the cell spacing phase places the cells and routing as close together as rules allow.
The assembly process guarantees that no geometrical design rules will be violated and that the proper connections will be made. In other tile-based module generation systems, the user must manually check to make sure that all possible combinations of tiles will fit together properly. This is impractical for module generators that have a large number of tiles and options. The connection operator automatically ensures that the proper connections will be made and that no geometrical design rules will be violated.
- ENTRY
- October 28, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-180.tif)
- U of California Berkeley, CS csd-87-312(dir)
- Raghavan, Prabhakar. ``Randomized Rounding And Discrete Ham-Sandwich Theorems: Provably Good Algorithms For Routing And Packing Problems.'' UCB//CSD-87-312, July 1986. 73 pages.
- ABSTRACT
- This thesis deals wiht the approximate solution of a class of zer0-one integer programs arising in the design of integrated circuits, in operations research, and in some combinatorial problems. Our approach consists of first relaxing the integer program to a linear program, which can be solved by efficient algorithms. The linear program solution may assign fractional values to some of the variables, and these values are 'rounded' to obtain a provably good approximation to the original integer program.
We first consider the problem of global routing in gate-arrays. This problem has important applications in the design of integrated circuits, and can be formulated as a zero-one integer program. We introduce a technique we call randomized rounding for producing a provably good approximation to this integer program from the solution to its relaxation. In order to prove the quality of this approximation, we make use of some new bounds on the tail of the binomial distribution. We present the results of experiments conducted on industrial gate=arrays using our methods; these are encouraging and call for further work.
We then show that our randomized rounding technique can be applied to some problems in combinatorial optimization and operations research. We also describe the relation between the problems we study and a class of combinatorialresults known as "discrete ham-sandwich theorems". This leads to the problem of rounding linear program solutions deterministically mimic the randomized algorithm in a certain precise sense. This leads us to the development of a deterministic polynomial time rounding algorithm that yields the same performance guarantees as the random ized method.
- ENTRY
- March 25, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-073}.tif)
- U of California Berkeley, CS csd-86-291(dir)
- Hamachi, Gordon Taro. ``An Obstacle-Avoiding Router for Custom VLSI.'' UCB//CSD-86-291, 130 pages.
- ABSTRACT
- Magic's automatic routing system combines the flexibility of hand-routing with the speed and quality of automatic channel routers, by allowing chip designers to prewire selected nets by hand. The router then works around this previously-placed layout, called obstacles, to automatically wire the remaining nets. This ability to partially hand-route an integrated circuit gives designers complete control over critical paths, power and ground routing, and other special netw. At the same time the router provides a fast way to make the remaining connections in the design.
The system's novel features include a fast channel decomposer, an obstacle-avoiding global router, and an obstacle-avoiding switching router. The router's channel decomposition algorithm relies on a corner-stitched data structure to efficiently produce a small number of large channels. The global router considers obstacles during path generation, trading-off net length and channel complexity to simplify the subsequent channel routing task. While able to cope with obstacles, Magic's switchbox router is still comparable to the best traditional (non-obstacle-avoiding) channel routers.
The router's obstacle-avoidance features rely on two underlying concepts: (1) a preferred direction for crossing an obstacle, and (2) hazards, or areas the routing should avoid. Crossing obstacles in the preferred direction minimizes the creation of blocked areas, which can not be crossed by other routing; this minimizes obstacles' impact on the automatic routing. Crossings in preferred directions are controlled by strategically-placed hazards adjacent to obstacles.
Measurements show that obstacle-avoiding routing is both useful and practical: hand-routing improves the electrical characteristics of the selected nets, while the hand-routing obstacles have only minor effects upon the routing quality of a design as a whole. The improvement in electrical characteristics is due to the decreased net length and increased attention to layer selection possible when nets are prewired by hand.
- ENTRY
- June 25, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-130}.tif)
- Ohio State U CIS TR22.ps.gz(67K)
- Schwiebert, Loren and Jayasimha, D.N. "A Necessary and Sufficient Condition for Deadlock-Free Wormhole Routing," 20 pp. (OSU-CISRC-4/94-TR22). Electronic report under 1994/TR22.ps.gz (THIS TR WAS UPDATED 12/94).
- International Computer Science Inst (Berkeley) tr-94-068.ps.Z(83K)
- Eyal Kushilevitz, Rafail Ostrovsky, Adi Rosen. ``LOG-Space Polynomial End-to-End Communication.'' ICSI-TR-94-068, International Computer Science Institute, Berkeley, CA, December 1994.
Communication between processors is the essence of distributed computing: clearly, without communication distributed computation is impossible. However, as networks become larger and larger, the frequency of link failures increases. The End-to-End Communication is a classical problem that asks how to carry out fault-free communication between two processors over a network, in spite of such frequent communication faults. The sole minimum assumption is that the two processors that are trying to communicate are not permanently disconnected (i.e., the communication should proceed even in the case that there does not (ever) simultaneously exist, at any time, any operational path between the two processors that are trying to communicate.) For the first time, we present a protocol which solves this fundamental problem with logarithmic-space and polynomial-communication at the same time. This is an exponential memory improvement to all previous polynomial-communication solutions. That is, all previous polynomial-communication solutions needed at least linear (in n, the size of the network) amount of memory per edge. Our algorithm maintains a simple-to-compute $O(\log n)$-bits potential function at each edge in order to perform routing, and uses a novel technique of packet canceling which allows us to keep only one packet per edge. We stress that both the computation of our potential function and our packet-canceling policy are totally local in nature; we believe that they are applicable to other settings as well
- U of California Berkeley, ERL erl-93-42(dir)
- Bhaqt, Narasimha B.; Chaudary, Kamal; Kuh, Ernest S. ``Performance-Oriented Fully Routable Dynamic Architecture for a Field Programmable Logic Device.'' UCB//ERL-93-42, 42 pages.
- ABSTRACT
- In this report we present a new architecture for a Field Programmable Logic Device. The architecture is geared towards routing completion and predictable timing performance. The central principle of the new architecture is based on the concept of efficient use of silicon resources. It is performance-oriented, with predictable interconnect and logic delays, and has a guaranteed routability. Latency in the original circuit is exploited in such a manner as to make efficient reuse of interconnect resources. Specifically, the given circuit is topologically levelized and implemented in a folded-pipeline manner. The new architecture is CAD friendly, thereby eliminating the need for complex tiem-consuming place and route tools.
- ENTRY
- November 30, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-042}.tif)
- U of California Berkeley, CS csd-92-689(dir)
- Tzeng, Ping-San. ``Integrated Placement and Routing for VLSI Layout Synthesis and Optimization.'' UCB//CSD-92-689, 106 pages.
- ABSTRACT
- This dissertation investigates ways to integrate various VLSI layout algorithms via carefully designed integrated data structures. Such an integrated approach can achieve better overall results by iterating non-sequentially among the various algorithms in a demand-driven manner. The shared data strucure which is modified incrementally by all the different algorithms serves as an efficient communication medium between them This approach has resulted in several new prototype tools, including a new placement program that combines wire-length optimization with a new 2-D compaction algorithm, a new area-routing approach that employs hierarchical rip-up and reroute techniques in an integrated global and detailed routing environment, and also a system that integrates the area router with a placement adjustment algorithm. This integrated system can iterate automatically between area routing and placement adjustment phases to generate optimized results for macro-cell problems with over-the-cell routing.
- ENTRY
- August 6, 1993
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-106}.tif)
- U of California Berkeley, CS csd-93-746(dir)
- Harchol, Mor; Black, Paul E. ``Queueing Theory Analysis of Greedy Routing on Square Arrays.'' UCB//CSD-93-746, 16 pages.
- ABSTRACT
- We apply queueing theory to derive the probability distribution on the queue buildup associated with greedy routing on an $n \times n$ array of processors. We assume packets continuously arrive at each node of the array with Poisson rate $\lambda$ and have random destinations. We assume an edge may be traversed by only one packet at a time and the time to traverse an edge is Poisson distributed wit mean $1$.
To analyze the queue size in steady-state, we formulate the problem into an equivalent Jackson queueing network model. It turns out that determining the probability distribution on the queue size at each node is then just a matter of solving $O(n^{4})$ simultaneous linear equations which determine the total arrival rate at each node and then plugging these arrival rates into a short formula for the probability distribution given by the queueing theory. However, we even eliminate the need to solve these simultaneous equations by deriving a very simple formula for the total arrival rates in the cas of greedy routing.
Lastly, we use this simple formula to prove that the expected queue size at a node of the $n \times n$ array increases as the Euclidean distance of the node from the center of the array decreases.
- ENTRY
- May 25, 1993
- RETRIEVAL
- postscript (in all.ps)
- U of California Berkeley, CS csd-93-756(dir)
- Harchol, Mor; Black, Paul E. ``Queueing Theory Analysis of Greedy Routing on Arrays and Tori.'' UCB//CSD-93-756, 26 pages.
- ABSTRACT
- We apply queueing theory to derive the probability distribution on the queue buildup associated with greedy routing on an n by n array and an n by n torus of processors. We assume packets continuously arrive at each node of the array or torus with Poisson rate lambda and have random destinations. We assume an edge may be traversed by only one packet at a time and the time to traverse an edge is exponentially distributed with mean 1.
To analyze the queue size in steady-state, we formulate both these problems as equivalent Jackson queueing network models. With this model, determining the probability distribution on the queue size at each node involves solving O(n^4) simultaneous linear equations. However, we eliminate the need to solve these simultaneous equations by deriving a very simple formula for the total arrival rates and for the expected queue sizes in the case of greedy routing.
This simple formula shows that in the case of the n by n array, the expected queue size at a node increases as the Euclidean distance of the node from the center of the array decreases. Furthermore, in the case of the $n \times n$ torus, the probability distribution on the queue size is identical for every node.
We also translate our results about queue sizes into results about the average packet delay.
- ENTRY
- June 10, 1993
- RETRIEVAL
- postscript (in all.ps)
- U of Massachusetts Amherst, CoInS UM-CS-1990-101.ps(164K)
- UM-CS-1990-101 General Routing on the Lowest Level of the Image Understanding Architecture Martin C. Herbordt, Charles C. Weems and David B. Shu May, 1990 Comments: there is a separate ps.file that inc.fig.5
- U of Massachusetts Amherst, CoInS UM-CS-1990-101.ps(164K)
- UM-CS-1990-101 General Routing on the Lowest Level of the Image Understanding Architecture Martin C. Herbordt, Charles C. Weems and David B. Shu May, 1990 Comments: there is a separate ps.file that inc.fig.5 A Task-Centered Theory of Cooperative Work
- U of Massachusetts Amherst, CoInS UM-CS-1991-063.ps(466K)
- UM-CS-1991-063 Practical Algorithms For Online Routing on SIMD Meshes M. Herbordt, J. Corbett, C. Weems and J. Spalding May, 1991 Comments:
- U of California Berkeley, ERL erl-93-81(dir)
- Lee, Brian Douglas Ngai. ``COMBINED HIERARCHICAL APPROACHES TO INTEGRATED CIRCUIT LAYOUT BASEd ON A COMMON DATA MODEL.'' UCB//ERL-93-81, November 1993. 110 pages.
- ABSTRACT
- The integrated circuit layout problem is the specification of fabrication patterns that implement a given circuit description subject to manufacturing and performance constraints. The high complexity of integrated circuits has made it necessary to decompose the layout problem into a set of subproblems, and the typical layout process usually solves a sequence of subproblems corresponding to the steps of floor planning, placement, channel definition, global routing, detailed routing, and compaction. Each subproblem depends on the solutions of the previous subproblems and iteration over the sequence of problems may be required to find a feasible layout solution. Unfortunately, iterative improvement of layout solutions is very difficult because a side effect of the partitioning is that feedback between subproblems is hard and not well understood.
A merged hierarichal approach to layout presented that provides a means of investigating the relationship between placement and routing to improve current layout methods. A common data model is used to integrate layout phases and to simplify and enhance information flow within the layout process. The data model induces a structure to the layout process for experimenting with feedback and information management.
A layout system based on a 2x2 grid-graph abstraction that combines placement and global routing has been implemented based on this paradigm. Examples from sea-of-gates designs are used for benchmark comparisons.
- ENTRY
- June 10, 1994
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-110}.tif)
- U of California Berkeley, ERL erl-93-80(dir)
- Bhat, Narasimha B. ``Novel Techniques for High Performance Field Programmable Logic Devices.'' UCB//ERL-93-80, November 1993. 232 pages.
- ABSTRACT
- Field programmable logic devices (FPLDs) are fast emerging as viable alternatives to mask programmed parts because of their rapid time-to-market and low costs. Their application has, however, been limited to implementing random logic, with non-critical timing specifications. This work attempts to advance FPLD usage to high-performance applications as well. A two-pronged approach is adopted. In the first part, CAD algorithms aimed at improving routability and performance of designs mapped to existing look-up table (LUT) based field programmable gate arrays (FPGAs) are developed. The concept of a two-input LUT primitive cell is introduced. This reduces the number of library patterns that require to be stored for an LUT library, and makes it feasible to extend performance-driven library based technology mapping techniques to LUT FPGAs. The performance- driven mapping algorithm accounts for interconnect delay and provides area-delay trade offs. Experiments on benchmark designs show the effectiveness of the new algorithms. In the second part, a new FPLD architecture is introduced. The architecture is based on the concept of time-sharing of logic and routing resources in an effort to have a fully routable, CAD friendly FPLD with predictable timing performance and efficient silicon usage. Real-time reconfiguration of logic and routing resources implements a given circuit in a folded pipe-line fashion, pipe lining at the gate level. Several possible variations of the basic architecture are discussed. A simple synthesis scheme is developed and experimental results are reported. Area and timing analyses demonstrates advantages over existing FPGAs.
- ENTRY
- June 9, 1994
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-232}.tif)
- U of California Berkeley, ERL erl-90-17(dir)
- Lee, Brian D.N. ``Experiments in Hierarchical Routing of General Areas.'' UCB//ERL-90-17, March, 1990. 132 pages.
- ABSTRACT
- The complexity and size of integrated circuit designs has increased dramatically in recent years. Accordingly, there is a need for design automation tools that can handle ever larger and more complex routing problems. The problems of interest have evolved from simple channels to switchboxes to general areas. Currently, there is great interest in solving general area routing problems because of the rising popularity of new design methodologies and the emergence of new manufacturing technologies. For example, the Sea-of-Gates design style with many layers of high-quality interconnect requires over-the-cell routing to achieve high circuit densities. The structure of such routing problems on the channelless gate array is clearly in the domain of general area routers. Similarly, the next generation PC board technology using silicon-on-silicon modules will also require a general area router. Because these complex routing problems are a manifestation of an overall increase in design complexity, routers must not only handle these general area problems but also interact with other design tools in a more sophisticated manner. In particular, the feedback between routing programs and placement programs must become more explicit and any approach developed for general area problems must take this interaction into consideration.
In this report, hierarchical decomposition is examined as a way to attack the general area routing problem. This divide and conquer method is a useful technique for managing complexity and in recent years has been applied to various routing problems. In particular, there are examples of this concept in channel routers [BP82, BP83a, HM85, HM89], switchbox routers [BP83b], and global routers [M584, LTW86, M586, Lau87]. This work describes a set of experiments that outlines the extension of these applications to general area routing problems.
- ENTRY
- Aug 31, 1994
- RETRIEVAL
- ocr (in all.ocr); tiff (in {001-132}.tif)
- U of Virginia CS&IPC CS-94-03.ps.Z(124K)
- [CS-94-03] J. L. Ganley and J. P. Cohoon, Optimal Rectilinear Steiner Tree Routing in the Presence of Obstacles, February 2, 1994.
- U of California Berkeley, CS csd-94-821(dir)
- Harchol-Balter, Mor; Wolfe, David. ``Greater Variance Does Not Necessarily Imply Greater Average Delay.'' UCB//CSD-94-821, July 1994. 16 pages.
- ABSTRACT
- Real-world packet routing differ in many ways from the networks which are analyzable by current-day queueing theory methods. For example the service distributions in real-world networks are constant, whereas the vast majority of queueing theory applies most powerfully to exponential service distributions. Consequently, it is desirable to at least be able to approximate the behavior of real-world networks by networks which we know how to analyze. Towards this end, much previous research has been done showing that for many networks greater variance (in service- time distributions and other things) leads to greater congestion, and therefore we can obtain upper bounds on delays in real-world networks by computing the delay in a related network, having more variance, which we know how to analyze. The class of networks for which greater variance leads to greater congestion is not known. This paper contributes to determining this classification by demonstrating a network for which increasing the variance in either of two very different ways leads to smaller delays. The arguments we make in this paper are not traditional to the field of queueing theory and are much more in the spirit of discrete mathematics.
- ENTRY
- October 19, 1994
- RETRIEVAL
- postscript (in all.ps)
- U of Maryland, College Park CS 3360(dir) 3360.ps.Z(105K)
- Cengiz Alaettinoglu, Ibrahim Matta, A. Udaya Shankar. ``A Scalable Virtual Circuit Routing Scheme for ATM Networks.'' CS-TR-3360, Dept. of Computer Science, Univ. of Maryland, College Park, MD, October 1994.
(Also cross-referenced as UMIACS-TR-94-115)
High-speed networks, such as ATM networks, are expected to support diverse quality-of-service (QoS) requirements, including real-time QoS. Real-time QoS is required by many applications such as voice and video. To support such service, routing protocols based on the Virtual Circuit (VC) model have been proposed. However, these protocols do not scale well to large networks in terms of storage and communication overhead
In this paper, we present a scalable VC routing protocol. It is based on the recently proposed viewserver hierarchy, where each viewserver maintains a partial view of the network. By querying these viewservers, a source can obtain a merged view that contains a path to the destination. The source then sends a request packet over this path to setup a real-time VC through resource reservations. The request is blocked if the setup fails. We compare our protocol to a simple approach using simulation. Under this simple approach, a source maintains a full view of the network. In addition to the savings in storage, our results indicate that our protocol performs close to or better than the simple approach in terms of VC carried load and blocking probability over a wide range of real-time workload
- Harvard CS tr-21-94.ps.gz(83K)
- Ted Nesson, Lennart Johnsson. ``ROMM Routing: A Class of Efficient Minimal Routing Algorithms.'' TR-21-94, 1994.
ROMM is a class of Randomized, Oblivious, Multi--phase, Minimal routing algorithms. ROMM routing offers a potential for improved performance compared to fully randomized algorithms under both light and heavy loads. ROMM routing also offers close to best case performance for many common permutations. These claims are supported by extensive simulations of binary cube networks for a number of routing patterns. We show that $k\times n$ buffers per node suffice to make k--phase ROMM routing free from deadlock and livelock on n--dimensional binary cubes
tr-21-94.ps.gz
- U of Massachusetts Amherst, CoInS UM-CS-1993-043.ps(966K)
- UM-CS-1993-043 Routing in High-Speed Networks Ren-Hung Hwang May, 1993 Comments: 4-004 Topological Reconstruction of a Smooth Manifold-Solid From Its Occluding Contour Lance R. Williams February, 1994 Comments:
- U of Massachusetts Amherst, CoInS UM-CS-1992-047.ps(168K)
- UM-CS-1992-047 On the Duality Between Routing and Scheduling Systems with Finite Buffer Space P.D. Sparaggis, C.G. Cassandras, D.F. Towsley June, 1992 January, 1993 Comments:
- U of Massachusetts Amherst, CoInS UM-CS-1992-047.ps(168K)
- UM-CS-1992-047 On the Duality Between Routing and Scheduling Systems with Finite Buffer Space P.D. Sparaggis, C.G. Cassandras, D.F. Towsley June, 1992 Practical Algorithms For Online Routing on SIMD Meshes M. Herbordt, J. Corbett, C. Weems and J. Spalding May, 1991 Comments:
- U of Massachusetts Amherst, CoInS UM-CS-1992-068.ps(4043K) UM-CS-1993-043.ps(966K)
- UM-CS-1992-068 A Transformational Approach to Database System Implementation Leonidas Fegaras (PhD Thesis) UM-CS-1993-043 Routing in High-Speed Networks Ren-Hung Hwang September, 1992 May, 1993 Comments: Comments:
- U of Illinois at Urbana-Champaign, CS UIUCDCS-R-94-1873.ps.Z(293K)
- 1887. Gao, Tong. "Performance driven placement and routing algorithms", Department of Computer Science Technical Report #1873, University of Illinois at Urbana-Champaign, Urbana, Illinois, 1994, p. 159.
- U of Cologne, M&CS zpr92-125.abstract(0K) zpr92-125.ps(102K) zpr92-125.ps.gz(29K)
- 92-125 A. Bachem and W. Hochst"attler and M. Malich Simulated Trading -- A New Parallel Approach For Solving Vehicle Routing Problems
- U of Washington CS UW-CSE-94-07-03.PS.Z(116K)
- UW-CSE-94-07-03.PS.Z 119K CHINN,LEIGHTON,TOMPA Minimal Adaptive Routing on the Mesh with Bounded Queue Size
- Stanford U, Heuristic Prog Proj shade-cera.ps(218K) shade-overview.html(83K)
- SHADE: Technology for Knowledge-Based Collaborative Engineering
James G. McGuire, Daniel R. Kuokka, Jay C. Weber, Jay M. Tenenbaum, Thomas R. Gruber, Gregory R. Olsen. Journal of Concurrent Engineering: Applications and Research (CERA), 1(2), September 1993.
Available as: shade-cera.ps, shade-overview.html
Abstract: Effective information sharing and decision coordination are vital to collaborative product development and integrated manufacturing. However, typical special-purpose CAE systems tend to isolate information at tool boundaries, and typical integrated CAE systems tend to limit flexibility and process innovation. The SHADE (SHAred Dependency Engineering) project strikes a balance between these undesirable extremes by supporting reconfigurable exchange of engineering knowledge among special-purpose CAE systems. SHADE's approach has three main components: a shared knowledge representation (language and domain-specific vocabulary), protocols supporting information exchange for change notification and subscription, and facilitation services for content-directed routing and intelligent matching of information consumers and producers. This report gives an overview and selected details of the progress through year two of the SHADE project.
T
- Stanford U, Heuristic Prog Proj musen-dimensions.binhex(207K) musen-dimensions.rtf(216K) shade-overview.html(83K)
- SHADE: Technology for Knowledge-Based Collaborative Engineering
Kuokka, D.R., McGuire, J.G, Weber, J.C., Tenenbaum, J.M., Gruber, T.R. and Olsen, G.R., SHADE: Knowledge-Based Technology for the Re-Engineering Problem - 1993 Annual Report.
A variant on the published paper above
Available as: shade-overview.html
Abstract: Effective information sharing and decision coordination are vital to collaborative product development and integrated manufacturing. However, typical special-purpose CAE systems tend to isolate information at tool boundaries, and typical integrated CAE systems tend to limit flexibility and process innovation. The SHADE (SHAred Dependency Engineering) project strikes a balance between these undesirable extremes by supporting reconfigurable exchange of engineering knowledge among special-purpose CAE systems. SHADE's approach has three main components: a shared knowledge representation (language and domain-specific vocabulary), protocols supporting information exchange for change notification and subscription, and facilitation services for content-directed routing and intelligent matching of information consumers and producers. This report gives an overview and selected details of the progress through year two of the SHADE project.
T
Dimensions of knowledge sharing and reuse
M. A. Musen. (1992). Dimensions of knowledge sharing and reuse. Computers and Biomedical Research, 25, 435-467.
Available as: musen-dimensions.rtf, musen-dimensions.binhex
Abstract: Many workers in medical informatics are seeking to reuse knowledge in new applications and to share encoded knowledge across software environments. Knowledge reuse involves many dimensions, including the reapplication of lexicons, ontologies, inference syntax, tasks, and problem-solving methods. Principal obstacles to all current work in knowledge sharing involve the difficulties of achieving consensus regarding what knowledge representations mean, of enumerating the context features and background knowledge required to ascribe meaning to a particular knowledge representation, and of describing knowledge independent of specific interpreters or inference engines. Progress in the area of knowledge sharing will necessitate more practical experience with attempts to interchange knowledge as well as better tools for viewing and editing knowledge representations at appropriate levels of abstraction. The PROTEGE II project is one attempt to provide a knowledge-base authoring environment in which developers can experiment with the reuse of knowledge-level problem-solving methods, task models, and domain ontologies.
T
- U of Washington CS UW-CSE-94-06-05.PS.Z(215K)
- UW-CSE-94-06-05.PS.Z 221K TOMPA Lecture Notes on Message Routing in Parallel Machines
- International Computer Science Inst (Berkeley) tr-94-024.ps.Z(107K)
- Ron Widyono. ``The Design and Evaluation of Routing Algorithms for Real-time Channels.'' TR-94-024, International Computer Science Institute, Berkeley, CA, June 1994.
The Tenet Scheme specifies a real-time communication service that guarantees performance through network connections with reserved resources, admission control, and rate con- trol. Within this framework, we develop and eval uate algo- rithms that find routes for these multicast connections. The main goals a establishment of the routed connection, to maximize the use- ful utilization of the network, and to be timely. The prob- lem to be solved is finding a minimum cost tree where each source to destination path is constrained by a delay bound. This problem is NP-complete, so heuristics based mainly on minimum incremental cost are developed. Algorithms we develop use those heuristics to calculate paths that are merged into a tree. We evaluate our design decisions through simulation, measuring success through the number of successfully established connections
- U of Toronto CE phd.ps.tar.Z(486K)
- StephenBrown/phd.ps.tar.Z
"Routing Algorithms and Architectures for Field-Programmable Gate Arrays" PhD dissertation, Stephen Brown brown@eecg.toronto.edu
---------------------------
- Princeton U CS 384.ps.Z(158K)
- TR-384-92 Finding All Minimal Shapes in a Routing Channel
- U of Cologne, M&CS zpr93-139.abstract(0K) zpr93-139.ps(427K) zpr93-139.ps.gz(117K)
- 93-139 A. Bachem and Hochst"attler and M. Malich The Simulated Trading Heuristic for Solving Vehicle Routing Problems
- U of California Berkeley, Sequoia s2k-92-15(dir)
- Pasquale, Joseph; Fall, Kevin R.; Forrest, Jon. ``Sequoia 2000 Network (S2Knet) Handbook.'' UCB//S2K-92-15, June 6, 1992. 14 pages.
- ABSTRACT
- The construction of the Sequoia 2000 network (S2Knet) is a joint effort involving people from the University of California campuses of Berkeley, Los Angeles, San Diego, and Santa Barbara, the UC Office of the Presi- dent (UCOP), and the San Diego Supercomputer Center (SDSC). The purpose of this handbook is to serve as a reference, containing up-to-date information describing policy, topology, names, addresses, and routing. It also includes a list of contacts for network management.
- ENTRY
- February 18, 1994
- RETRIEVAL
- postscript (in all.ps)
- U of Queensland, CS TR0283.ps.Z(42K)
- TR0283.ps.Z
TITLE: Optimal Distributed Algorithms for Constructing a Depth-First-Search Tree
AUTHORS: S. A. M. Makki and George Havas
ABSTRACT: We present more efficient distributed depth-first-search algorithms which construct a depth-first-search tree for a communication network. The algorithms require $|V|(1+r)$ messages and $|V|(1+r)$ units of time in the worst case, where $|V|$ is the number of sites in the network, and $0\leq r<1$~. The value of $r$ depends on the network topology and possibly on the routing chosen. In the best case, when the underlying network has a ring topology, $r=0$ and our basic algorithm requires $|V|$ messages and time units, regardless of routing. We extend this algorithm to achieve the same best case bound for other topologies. The worst case bound, which has $r= 1-2/|V|$, applies if the network topology is a tree. The improvement over the best of previous algorithms is achieved by dynamic backtracking, with a minor increase in message length.
(This report is to appear in Proc. ICPP'94 -- International Conference on Parallel Processing)
- INRIA (Natl Inst Res Comp & Ctl Sci, France) RR-2233.ps(278K) RR-2233.ps.gz(90K)
- RR-2233.ps.gz Liu (Z.),Mussi (P.) : Deadlock free routing on a ring : a performance evaluation
- U of Virginia CS&IPC CS-94-12.ps.Z(271K)
- [CS-94-12] Michael J. Alexander and Gabriel Robins, New Graph Arborescence and Steiner Constructions for High-Performance FPGA Routing, April 11, 1994.