Hypercomputer

Details Hypercomputer Hypercomputer

2000-03-30

2003-09-16

Treat, William M. (Department: 2183)

Electrical computers and digital processing systems: processing

Processing architecture

Array processor

C712S010000

Reexamination Certificate

active

06622233

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to (re)configurable computing systems.
2. Description of the Related Art
Introduction
Villasenor and Magnione, Configurable Computing, Scientific American, June 1997, pages 66-71, describe the new era of computer design opened by computers that modify their hardware circuits as they operate. Configurable computing architectures combine elements of general-purpose computing and application-specific integrated circuits (ASICs). The general-purpose processor operates on fixed circuits that perform multiple tasks under software control. An ASIC contains circuits specialized to a particular task and often needs little or no software to instruct it. In a configurable computer, software commands can alter field programmable gate array (FPGA) circuits as needed to perform a changing variety of tasks.
The promise of configurable circuits is versatile configuration for optimal performance of very specific tasks. On the one hand, a configurable computer often is more versatile than a special purpose device such as an ASIC which may not be configurable to perform a wide range of tasks. On the other hand, a configurable computer, or perhaps an array of programmable elements, often can be configured to perform specialized functions faster than a general purpose processor. A configurable computer can be optimally configured for the task at hand; whereas a general purpose processor suited to a wide variety often may not be optimized for a particular task.
U.S. Pat. Nos. 5,361,373 and 5,600845, both issued to Gilson, entitled INTEGRATED CIRCUIT COMPUTING DEVICE COMPRISING DYNAMICALLY CONFIGURABLE GATE ARRAY HAVING A MICROPROCESSOR AND RECONFIGURABLE INSTRUCTION EXECUTION MEANS AND METHOD THEREFOR, discloses an integrated circuit computing device comprised of a dynamically configurable Filed programmable Gate Array (FPGA). This gate array is configured to implement a RISC processor and a Reconfigurable Instruction Execution Unit.
The Challenge of Reconfigurable Communications Among (Re)Configurable Processing Elements
An important challenge in the development of computer systems in general, and in (re)configurable computing systems in particular, is communication among processing elements (e.g., FPGAs) that comprise the system. The ability to reconfigure processing elements to perform different tasks generally requires the ability to also (re)configure communication among processing elements to meet the needs of the task at hand. The following patents illustrate just a few prior solutions to the problem of reconfiguring communication among reconfigurable processing elements.
U.S. Pat. No. 5,020,059, issued to Gorin et al., entitled RECONFIGURABLE SIGNAL PROCESSOR, discloses an interconnection scheme among processing elements (PEs) of a multiprocessor computing architecture; and means utilizing the unique interconnections for realizing, through PE reconfiguration, both fault tolerance and a wide variety of different overall topologies including binary trees and linear systolic arrays. (See Abstract) The reconfigurability allows many alternative PE network topologies to be grown or embedded in a PE lattice having identified PE or inter-PE connection faults. In one embodiment, 4-port PEs are arrayed in a square 4×4 rectangular lattice which constitutes a basic 16-PE module. In one embodiment, each PE includes a digital signal processor, a memory and a configuration network. Each PE has four physical ports which connect to similar ports of its neighbors. For tree topologies, any of the four neighbors of a given PE may be selected as the parent of the given PE; and any or all of the remaining three neighboring PEs may be selected as the child(ren) PEs. (Column
2
, lines
56
-
64
) The functionality of the ports of each PE, which define the neighbor relations, may be controlled by instructions from an exterior source, such as a Host computer. The process of routing among ports within each PE may be software defined. By using a variant of a tree expansion scheme, the processor allows for virtually arbitrary up-sizing of the PE count to build virtually any size of tree network, with each size exhibiting the same degree of fault tolerance and reconfigurability. (Column
3
, lines
1
-
14
)
Gorin et al. assert that, importantly, their processor retains a logarithmic communications radius and uses identical and scale-invariant modules to grow. A property related to scale, is fast communications between a Host computer and the PE array. (Column
7
, lines
22
-
24
) PE configurations assembled as a binary tree, for example, have the advantageous property that if the number of PEs in the array are doubled, the layers through which communications must pass, increase by only one. This property, known as logarithmic communications radius, is desirable for large-scale PE arrays since it adds the least additional process time for initiating communications between Host and PEs. Salability is served by devising a single, basic PE port configuration as well as a basic module of board-mounted PEs, to realize any arbitrary number of PEs in an array. (Column
1
, line
61
-Column
2
, line
4
)
Gorin et al. also teaches a system comprising multiple printed circuit boards each mounted with 16 PEs. Each PE of the board has four ports. Two of the ports in each of the corner PEs in the lattice are available to effect communications external to the board. Further, each PE port communicates with one of the ports in the nearest neighbor PE.
FIG. 1
, which is from the Gorin et al. patent, shows three PE boards
1
,
2
and
3
with the port-to-port PE connections for a tree lattice structure. The PEs are shown not in their fixed lattice structure, but in the actual tree geometry for data flow, which can be created by configuring the PE ports. (Column
10
, line
64
-Column
11
, line
9
)
U.S. Pat. No. 5,513,371 issued to Cypher et al., entitled HIERARCHICAL INTERCONNECTION NETWORK ARCHITECTURE FOR PARALLEL PROCESSING, HAVING INTERCONNECTIONS BETWEEN BIT-ADDRESSABLE NODES BASED ON ADDRESS BIT PERMUTATIONS, describes two new classes of interconnection networks referred to as hierarchical shuffle-exchange (HSE) and hierarchical de Bruijn (HdB) networks. The new HSE and HdB networks are highly regular and scalable and are thus very well suited to VLSI implementation. These networks are efficient in supporting the execution of a wide range of algorithms on computers whose processors are interconnected via an HSE or HdB network. (Abstract)
FIG. 2
, which is from the Cypher et al. patent, depicts an illustrative drawing of a two level HSE computer including 8 processors interconnected via an HSE network.
FIG. 3
, which is from the Cypher et al. patent, depicts an illustrative drawing of a two level HdB computer including 8 processors interconnected via an HdB network. Each level of an HSE or HdB hierarchy corresponds to a level of packaging (e.g., the chip level, the board level, or the rack level). Their hierarchical nature allows them to be partitioned into a number of identical components (chips, boards, racks, etc.). The design of these components does not depend on the number of processors in the parallel machine, so they can be combined to form arbitrarily large networks. Also, because each level of the hierarchy corresponds to a level of packaging, the widths of the connections at each level of the hierarchy can be matched to the constraints imposed by the corresponding level of packaging. As a result, these networks are efficient in implementing a wide range of algorithms. (Column
6
, lines
32
-
44
)
U.S. Pat. No. 5,661,662 issued to Butts et al., entitled STRUCTURES AND METHODS FOR ADDING STIMULUS AND RESPONSE FUNCTIONS TO A CIRCUIT DESIGN UNDERGOING EMULATION, discloses a plurality of electronically reconfigurable gate array logic chips interconnected via a reconfigurable interconnect, and electronic representations of large digital networks that are converted to take temporary operating hardware form on the interconnected chips. The

Affiliated with

Also associated with

Rating

Hypercomputer does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Hypercomputer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hypercomputer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3005344