US 5,689,722 A · Multipipeline multiprocessor system

Abstract

The multipipeline multiprocessor includes communication hardware and parallel communication algorithms that are free of contention but also optimal in the sense that communication time is minimized for any vector computation task. This apparatus makes use of a hypercube processor interconnection network that has the capability to transmit on all wires simultaneously. A set of optimal routing algorithms for any of a plurality of communication tasks are either computed or stored in a memory to direct the interprocessor communication. Each computation task is defined as a plurality of sub-tasks, each sub-task defining a particular hypercube interconnection of the processors. The execution of the plurality of sub-tasks on the hypercube interconnection network implements the computation task. Selecting the plurality of sub-tasks in a manner that interconnects the processors in a non-blocking manner also reduces the communication time, since the activation of the hypercube interconnections are expeditiously accomplished, since no crosspoint switch settings must be computed.

Claims30

Dependent claims

A multipipeline multiprocessor comprising a hypercube-like processor interconnection network capable of transmitting on all wires simultaneously, that interconnects P processors via bidirectional communication paths, each of said P processors having d inputs and d outputs, where d is equal to a positive integer no greater than log.sub.2 P, each of said processors comprises:

computing means;
memory means connected to said d outputs for transmitting data on selected ones of said d outputs;
network means, including a local switch, for connecting selected ones of said d inputs to said memory means to collate communications between said processor interconnection network and said memory means;
means for storing a plurality of connection maps, each of which maps from a defined computation task to a predefined interconnection of said d inputs and said d outputs;
and
wherein said computing means is responsive to a receipt of a computation task, for retrieving a one of said connection maps, corresponding to said received computation task, from said storing means to activate said network means and said memory means to interconnect said d inputs and said d outputs, respectively, as defined by said transmitted connection map.

3 more elements

In a multipipeline multiprocessor that comprises a hypercube-like processor interconnection network, capable of transmitting on all wires simultaneously, that interconnects P processors via bidirectional communication paths, each of said P processors having d inputs and d outputs, where d is equal to a positive integer no greater than log.sub.2 P, each of said processors comprising computing apparatus, a memory connected to said d outputs for transmitting data on selected ones of said d outputs, a network, including a local switch, for connecting selected ones of said d inputs to said memory to collate communications between said processor interconnection network and said memory, a method of interconnecting said d inputs and said d outputs comprising the steps of:

storing a plurality of connection maps in a map memory, each of which connection maps translates a defined computation task into a predefined interconnection of said d inputs and said d outputs;
and
retrieving, in response to a receipt of a computation task, a one of said connection maps, corresponding to said received computation task, from said map memory to activate said network and said memory to interconnect said d inputs and said d outputs, respectively, as defined by said transmitted connection map.

Dependencies are inferred from the claim text.

Multipipeline multiprocessor system

Life of this patent

Multipipeline multiprocessor system

Life of this patent

Abstract

Claims30