The smallest networks that can connect eight thousand processing elements and memory interfaces in a petaflops cryocomputer contain hundreds of thousands of 2/spl times/2 switching nodes. We have determined circuit costs, maximal throughput and average latency for feasible multistage banyan and multidimensional pruned ring mesh networks. Each can deliver 20000 single-word packets every 30 picoseconds, more than eight million gigabytes per second. Switching delays one-way through each network total 1 to 2 nanoseconds. Banyans have 2/3 the switching delays of the smallest meshes. However, banyan signal propagation delays are larger. The only candidate network needing less than 100 square meters in four connection layers is a pruned mesh of shape 18/spl times/18/spl times/55/spl times/55 with nearly one million nodes. The smallest banyan has one quarter as many nodes, but needs nearly twice the wiring area.

Computer networks and email are coming to every household today, much as they came to the best laboratories in 1980. What technology in the best labs today will be part of the social fabric in 2010?

Distributed Shared Memory (DSM) systems have been proposed to combine the programmability of traditional shared memory and the scalability of message-passing systems. Eager DSM systems can greatly reduce access latencies for remote data by keeping copies of shared values in local memory and updating them immediately whenever a shared datum changes. However, sharing all changes globally can limit the system performance. It is usually possible to transform a program into an equivalent form that generates much less traffic, and therefore executes much more efficiently. This paper describes a compile-time analysis model for transforming simple shared memory programs with parallelized loop structures into programs that are optimized for efficient execution on eager DSM systems.>

Introduces optimistic lock synchronization using the group write consistency (GWC) model. GWC guarantees strict ordering of all shared writes in a processor group. In optimistic synchronization, if a lock-requesting processor can assume that the lock is free, execution of mutually exclusive code starts immediately. A wrong assumption results in rollback. Shared variable updates remain in the group until the lock manager grants the lock to the requesting processor. By evaluating the time needed for three processors to execute mutually exclusive code, GWC can out-perform weak, release, and even entry consistency. Simulations of task management using exclusive access to a shared queue, also show much faster mutual exclusion with GWC. Optimistic mutual exclusion may further halve total delays in accessing shared resources.>

Decentralized operating systems that control large multicomputers need techniques to schedule competing parallel programs called task forces. Wave scheduling is a probabilistic technique that uses a hierarchical distributed virtual machine to schedule task forces by recursively subdividing and issuing wavefront-like commands to processing elements capable of executing individual tasks. Wave scheduling is highly resistant to processing element failures because it uses many distributed schedulers that dynamically assign scheduling responsibilities among themselves. The scheduling technique is trivially extensible as more processing elements join the host multicomputer. A simple model of scheduling cost is used by every scheduler node to distribute scheduling activity and minimize wasted processing capacity by using perceived workload to vary decentralized scheduling rules. At low to moderate levels of network activity, wave scheduling is only slightly less efficient than a central scheduler in its ability to direct processing elements to accomplish useful work.

Packet switching is a communication technology which has been used extensively in geographically distributed computer networks. It is also applicable to the communication subnetworks of compact multimicrocomputers known as network computers. This paper describes the use of the language Concurrent Pascal to build a packet-switching subsystem for the MICRONET network of DEC LSI-11 microcomputers. Examples of actual Concurrent Pascal source code taken from the system demonstrate the usefulness of high-level languages with abstract data types for complex communication software.

This paper compares nine network interconnection schemes and introduces "dual-bus hypercubes," a cost-effective method of connecting thousands of dual-port single-chip microcomputers into a room-sized information processing system, a "network computer." Each network node is a chip containing memory and a pair of processors for tasks and input/output. Nodes are linked by shared communication buses, each conceptually spanning a D-dimensional, W-wide hypercube of N = WD nodes. Each node shares two buses. Each bus is shared by up to W nodes. The number of bus connections per node is fixed to satisfy chip pin limitations.

MICROS is the distributed operating system for the MICRONET network computer. MICRONET is a reconfigurable and extensible network of 16 loosely coupled LSI-11 microcomputer nodes, connected by packet-switching interfaces to pairs of high-speed shared communication buses. MICROS simultaneously supports many users, each running multicomputer parallel programs. MICROS is intended for control of network computers of thousands of nodes.

With rapidly developing microprocessor technology, we can anticipate an entire microcomputer being contained on a single, low-cost LSI chip. It will be technically and economically feasible to interconnect thousands or millions of these microcomputers to form a very large and powerful machine—a Mega-Micro-Computer (MMC). This paper defines a system of interlocking buses allowing dense message flow within an MMC. Each microcomputer shares two buses; each bus is shared by sixteen computers. There is a simple algorithm for optimal routing of messages. Data activity on each bus is analytically determined as a function of network size and the spatial distribution of messages between nodes. MMCs are about equally efficient whether connected by buses or by Pierce rings. For equal line costs, an MMC can allow 200 times denser message flow than a million computer network structured like Illiac IV.

The discriminating content addressable memory (DCAM) is a modified content addressable memory (CAM). After the ``similar to'' search performed by the CAM, the modified memory searches in parallel for the highest value in a particular field across all words of the memory. Applications of DCAM can greatly speed up queue searches and scheduling processes in operating systems. Worst case DCAM query time for 1000 words is 2 μs. The number of extra gates required by a DCAM increases linearly with memory size.