The 20th century brought about an "information revolution" which has forever altered the way we work, communicate, and live. In the 21st century, it is hard to imagine working without an increasingly broad array of supporting technologies and the digital data they provide.The care, management, and preservation of this tidal wave of data has become an increasingly important focus for technology, standards, and policy development. How will we be listening to our music in the next 100 years? How will we sustain our personal and federal records? In the next 100 years, storage technologies will advance tens of generations, and the digital collections preserved on up-to- date storage technologies will need to transition through each new generation, and many times over.This panel will discuss the major challenges of digital preservation, a technology and policy "killer app" for ours and the next generations.

This talk will review the mission, activities, and recommendations of the “Blue Ribbon Panel on Cyberinfrastructure” recently appointed by the leadership on the U.S. National Science Foundation (NSF). The NSF invests in “people, ideas, and tools” and in particular is a major investor in basic research to produce communication and information technology (ICT) as well as its use in supporting basic research and education in most all areas of science and engineering. The NSF through its Directorate for Computer and Information Science and Engineering (CISE) has provided substantial funding for high-end computing resources, initially by awards to five supercomputer centers and later through $70 M per year investments in two partnership alliances for advanced computation infrastructures centered at the University of Illinois and the University of California, San Diego. It has also invested in an array of complementary R&D initiatives in networking, middleware, digital libraries, collaboratories, computational and visualization science, and distributed terascale grid environments.

The performance of maze-routing algorithms mapped onto linear systolic array hardware is examined. Cell expansions in the wavefront-expansion phase of maze routing are performed in parallel in each processing stage of the hardware as the routing grid streams through the processor array. The authors concentrate on optimizing the performance of single-net routing problems with respect to a given systolic hardware configuration. A heuristic called constant-increment framing is introduced as a simple method for scheduling all the required wavefront expansion steps on a pipeline of processors. One-layer and two-layer routers using this heuristic have been implemented on a prototype systolic processor. Experimental and theoretical comparisons suggest that the constant-increment heuristic exhibits performance within a factor of two of optimal over a range of hardware configurations, and is substantially easier to compute than the optimal solution.>

Architectures based on the vector-radix 2DFFT algorithm and hence can avoid the matrix transpose problem have been proposed. The unique feature of the proposed architectures is that the data can be driven into the arithmetic processors in a pipeline fashion. This paper presents a propotype chip, which has been designed in 2 μm NMOS technology, for the generalized butterfly unit. The chip is a two-stage pipelined processor. The design experience, timing information, and the chip features including four multipliers, one adder/subtracter and PLA controllers are presented.

Special-purpose hardware has been proposed as a solution to several increasingly complex problems in design automation. This paper examines a class of cellular architectures called raster pipeline subarrays--RPS architectures--applicable to problems in physical DA that are (1) representable on a cellular grid, and (2) characterized by local functional dependencies among grid cells. Machines with this architecture first evolved in conventional cellular applications that exhibit similarities to grid-based DA problems. To analyze the properties of the RPS organization in context, machines designed for cellular applications are reviewed, and it is shown that many DA machines proposed/constructed for grid-based problems fit naturally into a taxonomy of cellular machines. The implementation of DA algorithms on RPS hardware is partitioned into local issues that involve the processing of individual cell neighborhoods, and global issues that involve strategies for handling complete grids in a pipeline environment. Design rule checking and routing algorithms are examined in an RPS environment with respect to these issues. Experimental measurements for such algorithms running on an existing RPS machine exhibit significant speedups. From these studies are derived the necessary performance characteristics of RPS hardware optimized specifically for grid-based DA. Finally, the practical merits of such an architecture are evaluated.

Although many of the basic techniques of computer arithmetic have been known since the earliest days of electronic computing, there is a continuing need to re-evaluate them in the context of developments in VLSI circuit technology. Furthermore, recent work in complexity of algorithms, particularly the solution of recurrence relations, suggests new candidate structures for generating the carry vector and raises the questions as to their practicality in modern logic design practice.

This paper describes aspects of an arithmetic design system (ADS) to support the quantitative evaluation of alternate number systems with respect to a given application and realization technology. In computer arithmetic we are concerned with establishing a correspondence between abstract quantities (numbers) and some physical representation (symbols), and with simulating the operations on these symbols. The ADS is intended to help study the cost and performance of alternate simulations. A finite number system is a triple consisting of a symbol set (elements are called "digit-vectors"), an interpretation set, a mapping between these two sets, and a set of operators (digit-vector algorithms) defined on its symbol set. A set of these digit vector algorithms are proposed for conducting arithmetic design. A number system matrix defines the digit vector algorithm for numerous number systems and a method for computing time and space complexity of compositions of these algorithms is proposed. An example of how the system could be used to compare addition, with and without out-of-range detection, for three number systems is given.

The architecture of the Cytocomputer?, an existing special-purpose, pipelined cellular image processor, is described. A formalism used to express cellular operations on images is then given. Cellular image processing algorithms are then developed that perform (1) design rule checks (DRC's) on VLSI circuit layouts, and (2) Lee-type wire routing. Two sets of cellular image processing transformations for checking the Mead and Conway design rules and for Lee-routing have been defined and used to program the Cytocomputer. Some experimental results are shown for these cellular implementations.

This paper describes an evolving Arithmetic Design System (ADS) to support the quantitative evaluation of alternate number systems with respect to a given application and realization technology. In computer arithmetic we are concerned with establishing a correspondence between abstract quantities (numbers) and some physical representation (symbols), and with simulating the operations on these symbols. The ADS is intended to help study the cost and performance of alternate simulations. A finite number system is a triple consisting of a symbol set (elements are called "digit-vectors"), an interpretation set, a mapping between these two sets, and a set of operators (digit-vector algorithms) defined on its symbol set. A set of these digit vector algorithms are proposed for conducting arithmetic design. A number system matrix defines the digit vector algorithm for numerous number systems and a method for computing time and space complexity of compositions of these algorithms is proposed. An example of how the system could be used to compare addition, with and without overflow detection, for three number systems is given.

Component and time complexity measures in terms of number of gates and gate delays, respectively, are derived for two multioperand adder structures: a tree of carry-save adders and a tree of carry-lookahead adders. The parameters of the complexity measures are operand length, number of operands, and maximum fanin to the gates. The analysis involves a constructive derivation of the complexity of carry-lookahead networks including optimization by removal of redundant paths. An alternate measure of component complexity, number of packages with a given number of pinouts, rather than number of gates, is also presented.

This paper presents the results of one phase of a study concerning methods for addition of P>2 numbers, each encoded as a vector of digits (digit vector) of length N. Such multi-operand addition has been studied most often in the context of reducing a set of partial products to a single result in the implementation of multiplication. More generalized multi-operand addition, most notably in the form of inner product calculations is, however, central to numerous scientific applications of digital computers. Although multi-operand addition is trivially accomplished by accumulation (iteration in time) in any general purpose machine, demands for very high-speed computation, typified by 2- and 3-D signal processing prompt implementation of dedicated, hardware-intensive structures for multi-operand addition. This study, for example, is motivated in part by requirements for rapid simultaneous addition of up to 100, 16-bit operands in the design of a dedicated processor for real-time reconstruction of 3-D images of the beating heart and breathing lungs [1].

Developments Reported Prior to 1972. This paper reviews work related to the theory and application of higher-radix, non-restoring division as originally defined by Robertson in 1958 [1]. The class of division methods proposed by Robertson is described by the recursive relationship:

Formal education in computer architecture rests upon the integration of numerous specialized courses. One such course, a new laboratory concerning contemporary, register-transfer level digital design, is described. Design in the course proceeds at the level of interconnection of memories, arithmetic logic units, I/O interfaces, and buses, rather than at the individual gate level associated with traditional combinational and sequential logic design. The principle items of hardware used in the laboratory are DEC Register Transfer Modules, the DEC PDP/16M, and the INTEL SIM8-01 Microcomputer. Numerous software packages have been developed to support activities within the lab including an RTM simulator, a graphical simulation of an RTM control sequencer, a PDP/16M assembler, a microcode generator, and SIM8-01 utility routine, assembler, and simulator. During one fourteen-week term, students are expected to complete six assigned lab projects and one special project. Examples of projects are described. A critique based upon the students' reactions and the technician's experience with the equipment is given together with proposals for future additions to the course.

The work to date has provided analytic tools to help answer design questions about table look-up type quotient selectors, and also a means for computer-aided design of any particular version deemed feasible. Reference 4 describes the application of a quotient selector in the arithmetic units of ILLIAC III.

In keeping with the experimental nature of the Illinois Pattern Recognition Computer (ILLIAC III), the arithmetic units are intended to be a practical testing ground for recent theoretical work in computer arithmetic. This paper describes the use of redundant number systems and the design of a structure with which multiplication and division are executed radix 256. The heart of the unit is the stored-sign subtracter, a recently discovered member of the family of borrow-save subtracters and carry-save adders. A cascade of these subtracters, controlled by a multiplier recoder, provides multiplication. The same structure, controlled by a "model division" (a quotient recoder), performs division.

Abstract—The nature of a class of division techniques which permit the selection of quotient digits in digital division by the inspection of truncated versions of the divisor and partial remainder is reviewed in detail. Two types of mechanisms, or so-called model divisions, for the selection of quotient digits are introduced. For both types of techniques, analytic tools are suggested for determining the number of bits which must be inspected as a function of the radix and form of representation of quotient digits. The analysis accounts for the representation of the partial remainder in a redundant form such as the one produced by an adder-subtractor which eliminates carry-borrow propagation.