Rebel is a new algorithm for clustering gates into k-input function blocks for look-up table field-programmable gate arrays (FPGA's). The algorithm propagates functional dependencies forward through a logic network, combining gates into clusters according to a heuristic metric. Rebel does a good job of handling reconvergent circuits, duplicating logic when it makes sense to do so, in addition, Rebel is fast, computing good clusters in near-linear time.

Graphical visualization of algorithm behavior can be a powerful technique for assessing the effectiveness of different algorithms and heuristics, provided that the graphical user interface (GUI) can be prototyped and modified quickly. Visualization was used to prototype a placement and routing package for the MITRE digital transform machine (DTM), a reconfigurable logic array. Use of the galaxy, programming language and environment greatly simplified GUI construction, allowing the prototyper to concentrate on placement and routing algorithms instead of the details of conventional GUI programming.>

Topological sorting (rank ordering) is a highly useful technique for ordering a set of objects according to a precedence relation, producing an ordered list suitable for processing. Applications for topological sorting include compiled logic simulation and timing analysis. While topological sorting is easily accomplished for flat combinational logic networks, hierarchical logic can be difficult to order because feedback may appear in the hierarchical representation even though it is not present in an equivalent flattened representation. This paper presents a new general solution to this problem and describes an efficient algorithm for topological sorting even in the presence of such apparent loops. Its application to hierarchical functional simulation of combinational and synchronous sequential logic is also discussed.>

The Galaxy CAD environment provides unique capabilities for rapid implementation and incorporation of tools into an integrated CAD framework. The author discusses in detail how novel hierarchical simulators can be added. Simulators are separated into generic and specific components. Galaxy provides generic functions so that programmers need only implement application-specific details such as data representation. This greatly reduces the quantity of code and expertise required by programmers to add new tools. Galaxy simulators and I/O tools, such as waveform editors, utilize a common communication protocol so that any I/O tool can be used as the front end of any simulator. Arbitrary combinations of tools can cooperate in the interactive multiple window environment.>

The algorithms and techniques used in incremental scanning and parsing of the Galaxy language are presented. Incremental compilers, programming environments that feature instantaneous change processing as well as the execution time efficiency of compiled programs and code development using the Galaxy language are discussed. It is shown that the algorithms guarantee minimal rescanning and reparsing are space and time efficient and are easily adapted to any language of equivalent class, including such languages as C and Pascal.>

article Free Access Share on The GF11 supercomputer Authors: John Beetem IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NYView Profile , Monty Denneau IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NYView Profile , Don Weingarten IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY IBM T.J. Watson Research Center, P.O. Box 218, Yorktown Heights, NYView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 108–115https://doi.org/10.1145/327070.327139Published:01 June 1985Publication History 94citation465DownloadsMetricsTotal Citations94Total Downloads465Last 12 Months53Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF