Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Ultracomputers

IP.com Disclosure Number: IPCOM000128170D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15

Publishing Venue

Software Patent Institute

Related People

J. T. Schwartz: AUTHOR [+3]

Abstract

A class of parallel processors potentially involving thousands of individual processing elements is described. The architecture is based on the perfect shuffle connection and has two favorable characteristics: (1) Each processor communicates with a fixed number of other processors. (2) Important communication functions can be accomplished an time proportional to the logarithm of the number of processors. A number of basic algorithms for these "ultracomputers" are presented, and physical design considerations are discussed in a preliminary fashion.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 4% of the total text.

Page 1 of 41

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Ultracomputers

J. T. Schwartz New York University

A class of parallel processors potentially involving thousands of individual processing elements is described. The architecture is based on the perfect shuffle connection and has two favorable characteristics: (1) Each processor communicates with a fixed number of other processors. (2) Important communication functions can be accomplished an time proportional to the logarithm of the number of processors. A number of basic algorithms for these "ultracomputers" are presented, and physical design considerations are discussed in a preliminary fashion. Key Words and Phrases: parallelism, parallel computation, parallel algorithms CR Categories: 5.25,
6.21

1. THE OPPORTUNITY

Integrated circuit technology is evolving continuously and rapidly toward smaller elementary devices and denser, more complex functions on each single silicon chip. New processing and lithographic techniques may make it possible to fabricate chips containing 10' and 10' individual transistors. One such chip would contain more function than today's largest computers. The problem of utilizing this potentially enormous computing power effectively is steadily becoming more significant. However, the mere possibilities inherent in very- large-scale integration VLSI) do not themselves create adequate ways of exploiting this technology. rhe programming techniques now current, which are still shaped by the vanishing ra era in which computing power was a scarce resource to be used sparingly, are ill-sui suited to the opportunities opening up. Few significant architectural concepts reflecting the LSI potential have as yet appeared. Rapidly improving technology has generally been used to map established computer architectures into smaller and cheaper formats. Thus the milestones of progress have been 16K and 64K memory chips; 8-bit fast adders, shifters, and multipliers; 16-bit microcomputer chips; etc. This line of development will clearly culminate in a powerful 32-bit computer realized on just s few chips, but few new ways of using computational power have emerged from this development. How then can we hope to exploit LSI technology more adequately? Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. This work was supported in part by the Applied Mathematical Sciences Program of the U.S. Department of Energy under Contract DE-AC02-76ER03077 and in part by the National Science Foundation under Grant NSF-MCS76-00116. Author's address: Courant Institute of Mathematical Sciences, New York University, 251 Mercer Stree...