Search

Programs for integrated circuit layout typically have two phases: placement and routing. The router should produce as efficient a layout as possible, but of course the quality of the routhing depends heavily on the quality of the placement. On the other hand, the placement procedure ideally should know the quality of a routing before it routes the wires. In this talk we present an optimal solution for a practical, common version of this placement and routing problem. River routing is the problem of connecting in order a set of terminals a1,...,an on a line to another set b1,...,bn across a rectangular channel. Since the terminals are located on modules, the modules must be placed relative to one another before routing. This placement problem arises frequently in design systems like bristle-blocks where stretch lines through a module can effectively break it into several chunks, each of which must be placed separately. In this talk, we shall present concise necessary and sufficient conditions for wirability which are applied to reduce the optimal placement problem to the graph-theoretic single-source-longest-paths problems. By exploiting the special structure of graphs that arise from the placement problem for rectilinear wiring, an optimal solution may be determined in linear time.

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1980., MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING, Bibliography: leaf 45., by Ron Yair Pinter., M.S.

The parallelization techniques embodied in source to source tools (that are customarily applied to FORTRAN programs) and in compilers for high level functional languages (such as Crystal) can and should be combined under a common framework. traditionally, the former tools target shared memory machines, whereas the latter - distributed memory (or data parallel) machines. One effect of the combination is the ability to run sequential FORTRAN programs on a whole new class of machines; it also provides a good way to separate between different parallelization concerns and deal with them at the appropriate level. We describe the design and an implementation of a prototypical system that enables such a combination. The design is modular and extendible; its implementation entails, among other challenges, bridging the gap between imperative and functional program semantics. We have developed several techniques that solve these and other fundamental problems, and present them with this concrete framework. Experimental results, as achieved by the prototype and as presented hereby, are most encouraging and substantiate the usefulness of this approach., Funded in part by NSF Grant no. CCR-8908285.