Method and system for converting a single-threaded software program into an application-specific supercomputer

• US 9,495,223 B2
• Filed: 12/23/2014
• Issued: 11/15/2016
• Est. Priority Date: 11/15/2011
• Status: Active Grant

• Current Assignee: Global Supercomputing Corporation
• Original Assignee: Global Supercomputing Corporation
• Inventors: Ebcioglu, Kemal, Kultursay, Emre
• Primary Examiner(s): Chen, Qing
• Application Number:
  US14/581,169
• Publication Number:
  US 20150317190A1
• Time in Patent Office: 693 Days
• Field of Search: 717136-161, 716/105, 716/116, 716/117, 716/124, 716/125, 716/128, 716/131
• US Class Current: 1/1
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: G06F 15/17381 Two dimensional, e.g. mesh, torus
• CPC Class Codes: G06F 2115/10 Processors
• CPC Class Codes: G06F 2212/455 Image or video data
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 30/30 Circuit design
• CPC Class Codes: G06F 30/323 Translation or migration, e.g. logic to logic, hardware description language [HDL] translation or netlist translation
• CPC Class Codes: G06F 30/392 Floor-planning or layout, e.g. partitioning or placement
• CPC Class Codes: G06F 8/40 Transformation of program code
• CPC Class Codes: G06F 8/4452 Software pipelining
• CPC Class Codes: G06F 8/452 Loops
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

The invention comprises (i) a compilation method for automatically converting a single-threaded software program into an application-specific supercomputer, and (ii) the supercomputer system structure generated as a result of applying this method. The compilation method comprises: (a) Converting an arbitrary code fragment from the application into customized hardware whose execution is functionally equivalent to the software execution of the code fragment; and (b) Generating interfaces on the hardware and software parts of the application, which (i) Perform a software-to-hardware program state transfer at the entries of the code fragment; (ii) Perform a hardware-to-software program state transfer at the exits of the code fragment; and (iii) Maintain memory coherence between the software and hardware memories. If the resulting hardware design is large, it is divided into partitions such that each partition can fit into a single chip. Then, a single union chip is created which can realize any of the partitions.

Claims

1. A general-purpose supercomputer for performing parallel execution of parallel software compiled from a code fragment within a single-threaded software application, where the general-purpose supercomputer comprises:

a. a plurality of general-purpose processors;

b. one or more task networks connected to the plurality of general-purpose processors, where each task network among the one or more task networks;

allows a first general-purpose processor on the task network to send a task invocation request to a second general-purpose processor on the task network, and

allows the first general-purpose processor on the task network to receive back either a task result message or a task completion acknowledgement from the second general-purpose processor on the task network;

c. at least one hardware synchronization unit to ensure that if a memory instruction instance I₂ is dependent on a memory instruction instance I₁ in sequential execution of the code fragment within the single-threaded software application, the memory instruction instance I₂ is executed after the memory instruction instance I₁ in the parallel execution of the parallel software performed by the general-purpose supercomputer; and

d. at least one coherent memory hierarchy, which;

(i) supports a plurality of load/store ports that are accessed by the plurality of general-purpose processors in parallel; and

(ii) signals a completion of each memory instruction issued from each load/store port of the plurality of load/store ports, for supporting synchronization units;

where the parallel execution of the parallel software by the general-purpose supercomputer is functionally equivalent to the sequential execution of the code fragment within the single-threaded software application; and

where the general-purpose supercomputer is implemented as a plurality of copies of a union module implemented in ASIC technology, with scalable network connections, and where the union module implemented in ASIC technology is able to perform function of any of a plurality of modules resulting from partitioning a hardware design of the general-purpose supercomputer.

2. The general-purpose supercomputer of claim 1, where each general-purpose processor p implements a general-purpose hardware Instruction Set Architecture including at least:

a send instruction that allows a general-purpose processor p to send a task invocation request to another general-purpose processor p′

over a task network, or that allows the general-purpose processor p to send a store-to-memory request to a coherent memory hierarchy, where a destination register of the send instruction is a quiescence register of p; and

one or more quiescence registers of p serving as synchronization units, where for each quiescence register q of p;

q is initially 1; and

when q is 1 and a send instruction whose destination register is q is executed by the general-purpose processor p, q is set to 0; and

when q is 0 and completion acknowledgements have been received back by the general-purpose processor p for all send instructions previously executed by the general-purpose processor p with the same destination register q, q is automatically set to 1 by the hardware Instruction Set Architecture, without executing any instructions; and

any instruction of the general-purpose processor p using one or more quiescence registers of p as source operands waits until all quiescence register source operands are 1, before starting execution.

3. The general-purpose supercomputer of claim 2, where at least one general-purpose processor is implemented using a Very Long Instruction Word processor architecture, for achieving fine grain parallelism within a task.

4. The general-purpose supercomputer of claim 2, where at least one general-purpose processor is implemented using a superscalar processor architecture, for achieving fine-grain parallelism within a task.