Parallel hardware hypervisor for virtualizing application-specific supercomputers

• US 20130205295A1
• Filed: 02/04/2012
• Published: 08/08/2013
• Est. Priority Date: 02/04/2012
• Status: Active Grant

• Current Assignee: Global Supercomputing Corporation
• Original Assignee: Global Supercomputing Corporation
• Inventors: Ebcioglu, Kemal, Dogan, Atakan, Altug, Reha Oguz, Lipasti, Mikko Herman, zkural, Eray
• Granted Patent: US 9,465,632 B2
• Time in Patent Office: Days
• US Class Current: 718/1
• CPC Class Codes: G06F 15/7871 Reconfiguration support, e.g. configuration loading, configuration switching, or hardware OS
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/5077 Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A parallel hypervisor system for virtualizing application-specific supercomputers is disclosed. The hypervisor system comprises (a) at least one software-virtual hardware pair consisting of a software application, and an application-specific virtual supercomputer for accelerating the said software application, wherein (i) The virtual supercomputer contains one or more virtual tiles; and (ii) The software application and the virtual tiles communicate among themselves with messages; (b) One or more reconfigurable physical tiles, wherein each virtual tile of each supercomputer can be implemented on at least one physical tile, by configuring the physical tile to perform the virtual tile'"'"'s function; and (c) A scheduler implemented substantially in hardware, for parallel pre-emptive scheduling of the virtual tiles on the physical tiles.

Claims

1. A hypervisor system for virtualizing application-specific supercomputers, the system comprising:

a. At least one software-virtual hardware pair consisting of a software application, and an application-specific virtual supercomputer for accelerating the said software application, wherein;

i. The virtual supercomputer comprises one or more virtual tiles; and

ii. The software application and the virtual tiles communicate among themselves with messages;

b. One or more reconfigurable physical tiles, wherein each virtual tile of each virtual supercomputer can be implemented on at least one physical tile, by configuring the physical tile to perform the virtual tile'"'"'s function; and

c. A scheduler implemented substantially in hardware, for parallel pre-emptive scheduling of the virtual tiles on the physical tiles.

2. A method for automatically converting a single-threaded software application into an (application, virtual supercomputer) pair integrated into the hypervisor system of claim 1, wherein the method comprises:

a) Converting an arbitrary code fragment from the single-threaded software application into customized non-virtual supercomputer hardware whose execution is functionally equivalent to the software execution of the code fragment;

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.

c) Partitioning the non-virtual supercomputer obtained in steps a) and b) into multiple modules;

d) Creating a union module which is capable of realizing any of the modules created by step c) depending on the configuration parameters provided to the union module;

e) Creating an (application, virtual supercomputer) pair wherein;

i. The application part of the said pair is the single-threaded software application as modified in step b);

ii. The virtual supercomputer part of the said pair consists of virtual tiles, each of which is a module obtained in step c);

f) Adding the functionality to stop, start, read the internal state, and write the internal state of the union module of step d);

to create the physical tile capable of realizing any among the set of virtual tiles of step e); and

g) Integrating at least one copy of the physical tile obtained in step f) within the hypervisor system of claim 1, to realize the said (application, virtual supercomputer) pair within the hypervisor.

3. The hypervisor system of claim 1, where the system further comprises:

a. A table mapping each virtual tile

i. to NULL, if the virtual tile is not currently contained in any physical tile;

ii. to the physical tile the virtual tile is currently contained in, otherwise;

b. A first level cache for the said table near each physical tile, mapping message destination virtual tiles to message destination physical tiles, such that when sending a message from a message source virtual tile v0 contained in a message source physical tile p0, to a message destination virtual tile v contained in a message destination physical tile p;

The message source physical tile p0 containing the message source virtual tile v0

can send a message directly and efficiently to

the message destination physical tile p containing the message destination virtual tile v

by

adding a field containing p to the message as it leaves the source virtual tile v0 contained in p0,

using the p field for routing the message toward the destination virtual tile v contained in p, through a scalable network, and

reverting the message back to its original form when the destination virtual tile is reached,

whenever v is found to be mapped to p in the first level cache near the message source physical tile p0.

4. The hypervisor system of claim 3, further comprising:

a. A monitor unit for implementing a tile replacement policy, by

i. Collecting statistics from physical tiles;

ii. Analyzing the statistics; and

iii. When any request arrives at the monitor unit for a physical tile to replace, responding with the best physical tile to replace based on the said tile replacement policy.

5. The hypervisor system of claim 4, further comprising:

a. A plurality of owner units each responsible for searching a part of the table, where the parts do not overlap and together constitute the entire table, such that when the message source physical tile p0 fails to find the message destination virtual tile v in the first level cache near p0, the owner unit o0 responsible for v searches for v in its own part of the table in order to resolve the first level cache miss, as follows;

i. If the owner unit o0 finds virtual tile v to be mapped to physical tile p in its part of the table;

1. The first level cache near the message source physical tile p0 is updated to include the (v to p) mapping;

2. The message is delivered directly from the message source physical tile p0 to the message destination physical tile p containing the message destination virtual tile v;

ii. Otherwise, if the owner unit o0 cannot find virtual tile v in its part of the table;

1. The owner unit o0 asks the monitor unit for a physical tile to replace;

2. If the physical tile p supplied by the monitor is already occupied by another virtual tile v′

, the owner unit o0 requests the owner unit of responsible for v′

;

a. To invalidate all first level cache entries in the system containing the (v′

top) mapping; and

b. To stop the physical tile p and save the state of the virtual tile v′

contained in p;

c. To remove the (v′

to p) mapping from o1'"'"'s part of the table;

3. The owner unit o0 inserts the (v to p) mapping in o0'"'"'s part of the table;

4. The owner unit o0 writes the last saved state of the virtual tile v into the physical tile p and restarts v where it left off;

5. The first level cache near the message source physical tile p0 is updated to include the (v to p) mapping;

6. The message is delivered directly from the message source physical tile p0 to the message destination physical tile p containing the message destination virtual tile v.

6. The hypervisor system of claim 5, further comprising a means for ensuring that given any two virtual tiles v1 and v2, the messages from v1 to v2 are not reordered during parallel operation.

7. The hypervisor system of claim 5, further comprising a means for ensuring that messages are not lost:

given two virtual tiles v1 and v2, whenever a message is sent from a virtual tile v1 to v2, the said message is always delivered to the virtual tile v2 during parallel operation.

8. The hypervisor system of claim 5, wherein the coherence among the table and the first level caches near the physical tiles is accomplished using directory-based cache coherence;

such that coherence messaging overhead is reduced.

9. The hypervisor system of claim 5, wherein the monitor implements a replacement policy complying with Service Level Agreements.

10. The hypervisor system of claim 1, wherein at least one physical tile is implemented in ASIC technology, and is capable of realizing any one of the virtual tiles of a virtual supercomputer, based on configuration parameters provided to the said physical tile.

11. The hypervisor system of claim 10, further comprising an adaptive method for allocating resources to ASIC physical tiles, the method comprising:

a) Determining the frequency of use of each (application, virtual supercomputer) pair over a recent time interval;

b) Searching for an (application, virtual supercomputer) pair that has the greatest frequency of use as determined in step a), such that

i. The pair is not already mapped to an ASIC physical tile; and

ii. The frequency of use of the said pair exceeds a threshold;

c) If such a pair could be found in step b), creating a new ASIC physical tile for this pair;

d) For each ASIC physical tile in the hypervisor system;

i. Increasing or decreasing the resources allocated to this ASIC physical tile, in order to make the allocated resources proportional to the average frequency of use of the (application, virtual supercomputer) implemented by this ASIC physical tile;

e) Repeating all of the steps above, periodically.

12. The hypervisor system of claim 1 wherein at least one (application, virtual supercomputer) pair is modified to implement a hardware-accelerated virtual operating system with external network connectivity, such that:

a. One virtual tile in the virtual supercomputer of the said pair comprises a general purpose microprocessor for running the operating system;

b. The remaining virtual tiles of the virtual supercomputer of the said pair implement the hardware acceleration of kernel codes and user application codes within the said operating system, and

c. The application part of the said pair is replaced by a network gateway connecting the said virtual tile containing the general purpose microprocessor, and optionally other virtual tiles of the said virtual supercomputer, to an external network.

13. The hypervisor system of claim 1, further comprising:

a capability to add a new (application, virtual supercomputer) pair to the system, or to delete such a pair from the system.

14. The hypervisor system of claim 1, further comprising the capability of:

a. Dividing at least one physical tile into a plurality of physical sub-tiles of possibly unequal sizes; and

b. During scheduling, allocating a virtual tile to a physical sub-tile that is large enough to accommodate the virtual tile;

for improving the utilization of physical tiles.

15. The hypervisor system of claim 1, further comprising a capability to restrict each virtual tile within a (software application, virtual computer) pair to communicate only with the other virtual tiles of the same virtual supercomputer and with the software application of the said pair, for achieving isolation of (application, virtual supercomputer) pairs within the hypervisor from one another.

16. The method of claim 2, further comprising the step:

while creating the virtual supercomputer from the software application of the said pair, synthesizing custom redundant checking circuits, such that the reliability of the physical tiles realizing the virtual tiles of the virtual supercomputer is increased.

17. A hypervisor system for virtualizing application-specific supercomputers, the system comprising:

a. At least one software-virtual hardware pair consisting of a software application, and an application-specific virtual supercomputer for accelerating the said software application, wherein;

i. The virtual supercomputer comprises one or more virtual tiles; and

ii. The software application and the virtual tiles communicate among themselves with messages;

b. One or more reconfigurable physical tiles, wherein each virtual tile of each virtual supercomputer can be implemented on at least one physical tile, by configuring the physical tile to perform the virtual tile'"'"'s function; and

c. Means for parallel pre-emptive scheduling of the virtual tiles on the physical tiles, wherein a scheduler is implemented substantially in hardware.