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

• US 20130125097A1
• Filed: 11/15/2011
• Published: 05/16/2013
• Est. Priority Date: 11/15/2011
• Status: Active Grant

• Current Assignee: Global Supercomputing Corporation
• Original Assignee: Global Supercomputing Corporation
• Inventors: Ebcioglu, Kemal, Kultursay, Emre, Kandemir, Mahmut Taylan
• Granted Patent: US 8,966,457 B2
• Time in Patent Office: Days
• US Class Current: 717/136
• 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 method to automatically convert a single-threaded software application into an application-specific supercomputer, the method comprising:

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.

2. The method in claim 1, further comprising the steps:

a. Converting a leaf region in the region hierarchy of the code fragment to a hardware finite state machine; and

b. Creating at least one copy of the finite state machine for the said region, and adding a network for communication with the state machines, such that the combined finite state machine copies and network behave as a single pipelined primitive operation for performing the function of the region.

3. The method of claim 2, further comprising the steps:

Recursively applying the method of claim 2 to the region hierarchy of the program, so that at each point where a parent region invokes a child region in the software execution, the finite state machine for the parent region initiates the primitive pipelined operation for the child region in the hardware execution.

4. The method in claim 3, further comprising:

creating customized hardware synchronization units for ensuring that if a memory instruction instance I₂ is dependent on a memory instruction instance I₁ in the software execution, the said instance of I₂ is executed after the said instance of I₁ in the hardware execution.

5. The method in claim 4, further comprising:

creating a coherent memory hierarchy that;

a. Supports a plurality of load/store ports that can be accessed in parallel; and

b. Signals the completion of each memory instruction issued from each port, for supporting synchronization units.

6. The method in claim 5, further comprising:

achieving synchronization using a quiescence detection synchronization unit.

7. The method in claim 5, further comprising:

achieving synchronization using a train crash synchronization unit.

8. The method in claim 5, further comprising:

achieving synchronization using a serializing synchronization unit.

9. The method in claim 5, further comprising:

achieving synchronization using a FIFO synchronization unit.

10. The method of claim 5, further comprising:

given a program region and a group of dependent loads and stores in the program region, achieving synchronization between the dependent loads and stores by a compiling a customized synchronization circuit, which emulates the behavior of snoopy write-update caches within the region body.

11. The method in claim 5, further comprising:

creating application-specific customized hardware for speculating that a dependence from the instance of memory instruction I₁ to the instance of memory instruction I₂ will not be observed at runtime;

executing the instance of second memory instruction I₂ speculatively without waiting for the instance of the first memory instruction I₁ to finish;

detecting an incorrect speculation if it occurs; and

recovering from the incorrect speculation by finally re-executing the said instance of I₂ after the said instance of I₁.

12. The method in claim 5, further comprising:

detecting and eliminating the communication of bits that are constant, dead, or redundant; and

reproducing the constant or redundant bits at the receiver side.

13. The method in claim 5, further comprising:

automatically identifying the code fragment in the software application that will be converted into hardware.

14. The method in claim 5, further comprising:

using software or hardware profiling feedback to assist in determining hardware subsystem parameters in future compilations.

15. The method in claim 5, further comprising:

creating application-specific customized hardware such that while a thread is waiting for the result of a network operation, other instructions from the same thread or from a different thread are executed, for better tolerating network latencies.

16. The method of claim 5, further comprising:

merging two networks with finite state machines performing distinct functions A and B, respectively;

by creating a common finite state machine which can perform both the A and B functions, for sharing resources.

17. The method of claim 16, where

a. The finite state machine capable of performing both the A and B functions is replaced by a general purpose microprocessor;

and

b. Optionally the finite state machine performing the A function is replaced by a general purpose microprocessor; and

c. Optionally the finite state machine performing the B function is replaced by a general purpose microprocessor.

18. The method of claim 5, further comprising the steps:

a. Compiling recursive region invocations within the code fragment, by making a finite state machine invoke the primitive pipelined operation for itself or for one if its ancestors;

b. If a finite state machine is not able to initiate an inner region hardware operation because of resource contention, making the finite state machine perform the requested inner region function itself, for avoiding deadlock.

19. The method of claim 5, further comprising:

applying frequency optimizations to finite state machines.

20. The method of claim 5, further comprising:

executing region invocations speculatively, and subsequently, when it is found that the speculative invocation was on the untaken path, canceling the speculative invocation.

21. The method in claim 5, further comprising:

applying symbolic execution with pointer analysis support and using its results to disambiguate dependences.

22. The method in claim 5, further comprising:

Using at least one butterfly sub-network, where the number of inputs and number of outputs of the sub-network is not limited to a power of two.

23. The method in claim 5, further comprising:

Using at least one task crossbar switch, where any number of requesting input ports and any number of accepting output ports are matched in parallel, in a single step.

24. The method of claim 5 further comprising:

maintaining precise exceptions in code fragments accelerated by the application-specific supercomputer.

25. The method of claim 5 further comprising:

converting a code fragment having a requirement selected from the group consisting of;

a. Memory mapped I/O;

b. Sequential multiprocessor consistency;

c. Accesses to volatile variables; and

d. Operating system kernel code execution;

into an application-specific supercomputer.

26. The method in claim 5, further comprising:

applying symbolic execution with pointer analysis support to achieve hardware optimizations.

27. The method in claim 5, further comprising:

creating a directory-based write-update cache whose design is simplified because of explicit synchronizations between dependent memory operations.

28. The method in claim 5, further comprising:

applying application-specific memory partitioning for reducing the number of cache ports, creating specialized cache memories, and reducing cache coherence hardware.

29. The method in claim 5, further comprising:

given that a region accesses any predictable sequence of addresses within a data structure, creating a streaming cache which computes the next address in the sequence locally on its own, and either supplies the next load data from that next address or accepts the next store data into that next address.

30. The method of claim 5, extended to the case where more than one code fragment within the software application is accelerated, by the following additional steps:

a. The host computer identifies the code fragment and entry point in a message sent to accelerator;

b. The accelerator receives the message and forwards it to the hardware sub-module for performing the function of the code fragment and entry point.

31. Using the method of claim 5, for converting

a. A hardware component pin specification, and

b. An arbitrary single-threaded sequential code fragment, where the code fragment comprises:

i. Instruction primitives for communicating with hardware component pins, and

ii. Locally declared data structures

into an application-specific hardware component having the specified pins, such that the hardware component is functionally equivalent to the said single-threaded sequential code fragment.

32. A method to convert a parallel application to an application-specific supercomputer by applying the method in claim 5 to each process in the parallel application.

35. An application-specific supercomputer obtained from a single-threaded software application with the method of claim 5.

33. A method to partition an application-specific supercomputer'"'"'s hardware design comprising a plurality of components and a plurality of networks connecting the components, into multiple modules, the method comprising:

a. Creating a scalable network for cross-module communication;

b. Partitioning the design into a plurality of modules, such that each component is placed into a particular module;

c. Placing an I/O controller in each module, for cross-module communication.

d. In each module,

for each network x that is originally attached to at least one component placed in this module,

creating a local sub-network of x connected to a port of the local I/O controller dedicated to network x, and also to the local components originally connected to network x.

e. Enabling the delivery of a message from any component on a network to any other component on the same network, as if the design were not partitioned, with the steps for cross-module message delivery comprising the following;

i. In the message source module, the message source component sends the message to the local I/O controller over the local sub-network of the said network;

ii. The message is sent outside the message source module by the local I/O controller, and gets routed within the cross-module communication network until it reaches the message destination module; and

iii. The message is accepted by the local I/O controller of the message destination module and gets delivered to the message destination component within the message destination module, over the local sub-network of the said network.

34. The method of claim 33, further comprising:

creating a single union module that can realize any of the partitions.