Heterogeneous multicore processor with graphene-based transistors

Techniques described herein generally include methods and systems related to the use of processors that include graphene-containing computing elements while minimizing or otherwise reducing the effects of high leakage energy associated with graphene computing elements. Furthermore, embodiments of the present disclosure provide systems and methods for scheduling instructions for processing by a chip multiprocessor that includes graphene-containing computing elements arranged in multiple processor groups.

CROSS REFERENCE TO RELATED APPLICATIONS

The present application is a U.S. National Stage filing under 35 U.S.C. § 371 of International Application No. PCT/US2013/055025, filed Aug. 15, 2013 and entitled “HETEROGENEOUS MULTICORE PROCESSOR WITH GRAPHENE-BASED TRANSISTORS.” The present application is also related to International Application No. PCT/US2013/055024, filed Aug. 15, 2013 and entitled “YIELD OPTIMIZATION OF PROCESSOR WITH GRAPHENE-BASED TRANSISTORS.” International Application No. PCT/US2013/055025 and International Application No. PCT/US2013/055024, including any appendices or attachments thereof, are hereby incorporated by reference in their entirety.

BACKGROUND

In keeping with Moore's Law, the number of transistors that can be practicably incorporated into an integrated circuit has doubled approximately every two years. This trend has continued for more than half a century and may be expected to continue until at least 2015 or 2020. However, simply adding more transistors to a single-threaded processor no longer produces a significantly faster processor. Instead, increased system performance has been attained by integrating multiple processor cores on a single chip to create a chip multiprocessor, and by sharing processes between the multiple processor cores of the chip multiprocessor. System performance and power usage can be further enhanced with chip multiprocessors that have core elements configured for multiple instruction sets or for handling different subsets of instruction sets.

SUMMARY

In accordance with at least some embodiments of the present disclosure, a chip multiprocessor comprises one or more high-speed processor cores disposed on a die and including graphene-containing computing elements. The high-speed processor cores are configured to operate when all other processor cores on the die that include a lower percentage of graphene-containing computing elements than the one or more high-speed processor cores are configured to be gated. The chip multiprocessor further comprises one or more additional processor cores disposed on the die and including a lower percentage of graphene-containing computing elements than the one or more high-speed processor cores.

In accordance with at least some embodiments of the present disclosure, a method to schedule instructions to be processed by a chip multiprocessor that includes graphene-containing computing elements arranged in multiple processor groups comprises determining at least one of a time cost, an energy cost, and a thermal cost for one or more of the multiple processor groups to execute a first block of instructions from an application and determining at least one of a time cost, an energy cost, and a thermal cost for one or more of the multiple processor groups to execute a second block of instructions from the application. The method may further comprise determining context switching costs associated with switching execution of the application from any one of the multiple processor groups to any other of the multiple processor groups, the context switching taking place after the first block of instructions is executed by a first of the multiple processor groups and before the second block of instructions is executed by a second of the multiple processor groups, and, based on at least one of the determined time cost, energy cost, and thermal cost and on the determined context switching costs, selecting one of the multiple processor groups to execute the first block of instructions and selecting one of the multiple processor groups to execute the second block of instructions.

In accordance with at least some embodiments of the present disclosure, a method to schedule instructions to be processed by a chip multiprocessor that includes graphene-containing computing elements arranged in multiple processor groups comprises determining at least one of a time cost, an energy cost, and a thermal cost for each of the multiple processor groups to execute a first block of instructions from an application and, based on at least one of the determined time, energy cost, and thermal cost, selecting a first of the multiple processor groups to execute the first instruction set. The method may further comprise determining at least one of a time cost, an energy cost, and a thermal cost for each of the multiple processor groups to execute a second block of instructions from the application, and, based on at least one of the determined time cost, energy cost, and thermal cost, selecting a second of the multiple processor groups to execute the second instruction set, the selecting of the second of the multiple processor groups being performed after the first of the multiple processor groups has begun execution of the first block of instructions.

DETAILED DESCRIPTION

This disclosure is generally drawn, inter alia, to methods, apparatus, systems, devices, and/or computer program products related to chip multiprocessors.

Briefly stated, techniques described herein generally include methods and systems related to the use of processors that include graphene-containing computing elements while minimizing or otherwise reducing the effects of high leakage energy associated with graphene computing elements. Furthermore, embodiments of the present disclosure provide systems and methods for scheduling instructions for processing by a chip multiprocessor that includes graphene-containing computing elements arranged in multiple processor groups.

There is a trend toward large-scale chip multiprocessors that include a relatively large number of processor cores, with core counts as high as hundreds or thousands envisioned in the near future. Such processors can greatly reduce processing time for applications that have high levels of concurrency, e.g., applications in which multiple computations can be executed simultaneously or in parallel with each other. However, the majority of applications are generally either “sequential,” e.g., unsuitable for parallel processing, or have large portions that are essentially sequential. Limited speed-up is feasible in running such sequential applications by using a chip multiprocessor, regardless of the number of parallel processes that can be supported thereby. For example, if 50% of an application is sequential, even if the execution time of the remaining code is reduced to a single clock cycle, no speed up by a factor higher than 2× may be possible. This effect is illustrated inFIG. 1.

FIG. 1is a diagram representing example relative execution times of a particular computer program when performed by three different configurations of chip multiprocessor: a processor unoptimized for parallel processing, a chip multiprocessor optimized for parallel processing, and a graphene-containing chip multiprocessor. Execution scheme110depicts execution of the computer program with respect to time using the processor unoptimized for parallel processing, execution scheme120depicts execution of the computer program with respect to time using the chip multiprocessor optimized for parallel processing, and execution scheme130depicts execution of the computer program with respect to time using the graphene-containing chip multiprocessor of one embodiment.

For illustrative purposes, the computer program includes a single sequential processing segment101and a single parallel processing segment102, although typically computer programs can include a plurality of each. Instructions in sequential processing segment101can be performed sequentially. For example, sequential processing segment101may include a high density of conditionals, thereby rendering parallel processing of the computer program in sequential processing segment101inapplicable or impractical. In contrast, instructions in parallel processing segment102can be performed in parallel without significant adverse effect on the execution of the computer program and may instead improve the execution of the computer program.

Execution scheme110illustrates that when the computer program is executed by the unoptimized processor, a total execution time110A may be, in this example, 100 sec: time101A of 50 seconds for executing sequential time segment101and 50 seconds for executing parallel processing segment102. As shown, sequential processing segment101may be performed sequentially with a single computing thread115. Parallel processing segment102is also performed sequentially with a single computing thread116, since the computer program is executed with the processor unoptimized for parallel processing and is unable to perform parallel processing.

Execution scheme120illustrates that when the computer program is executed by the chip multiprocessor optimized for parallel processing, execution time120A is less than total execution time110A (e.g., 100 seconds) of execution scheme110, and more than the time101A (e.g., 50 seconds) for execution of sequential processing segment101. For example, assuming that the chip multiprocessor optimized for parallel processing includes five cores, each configured to run one of parallel computing threads126, the execution time for execution scheme120is 60 seconds: 50 seconds for executing sequential time segment101with computing thread115and 10 seconds for executing parallel processing segment102with parallel computing threads126. Clearly, in this particular example, total execution time120A is not reduced below execution time101A by using the chip multiprocessor optimized for parallel processing, even if an unlimited number of computing threads126can be used.

Execution scheme130illustrates that when the computer program is executed by the graphene-containing chip multiprocessor that can be used in one embodiment, execution time130A can be significantly less than either total execution time110A of execution scheme110or total execution time120A of execution scheme120. Furthermore, according to embodiments of the disclosure, execution time130A can be significantly less than time101A used for execution of sequential processing segment101in execution schemes110and120. This is because a graphene-containing processor core of the multiprocessor may be configured to greatly reduce the time to complete the execution of sequential processing segment101. In some embodiments of the disclosure, a graphene-containing processor core may be configured to perform sequential processing segment101approximately 10 to 100 times faster than a processor core that includes fewer (or no) graphene-containing elements. Various examples of graphene-containing processor cores, configured according to one or more embodiments of the disclosure, are described below. Thus, even when parallel processing segment102is executed by the graphene-containing processor core using the same number of parallel computing threads126used in execution scheme120, execution time130A can be significantly less than total execution time120A of execution scheme120. For example, when time101A for execution of sequential processing segment101makes up the majority of total execution time120A, the duration of execution time130A may be a small fraction of total execution time120A, for example 1/10th or less, thereby providing a 10× or greater improvement in performance.

According to embodiments of the present disclosure, a chip multiprocessor includes one or more graphene-containing processor cores that utilize at least some graphene computing elements, such as transistors, in addition to one or more other processor cores that utilize non-graphene silicon transistors and other non-graphene computing elements. A graphene transistor may be a silicon transistor in which the channel of the transistor is formed using graphene. Graphene is an allotrope of carbon whose structure may be a single planar sheet of sp2-bonded carbon atoms that are densely packed in a honeycomb crystal lattice. Generally, all other components can be substantially identical to the components of a complementary metal-oxide semiconductor (CMOS) transistor. Hence, integration of graphene and CMOS transistors in a single processor may be relatively simple and inexpensive. Graphene transistors have numerous desirable properties, including compatibility with silicon transistors, great mobility (at least 10× higher than other transistors), and exceptional feature size scalability. Consequently, graphene transistors can be readily manufactured that operate at much higher speeds than other transistors, e.g., in the terahertz regime. Thus, the use of graphene-containing processors can greatly decrease execution time in highly sequential software applications, such as illustrated inFIG. 1. In addition, graphene transistors may have significantly lower switching energy than silicon transistors, making them well-suited for use in mobile devices or other situations in which energy consumption may be an issue.

However, graphene transistors may have significantly higher leakage than silicon transistors, for example on the order 100,000-5,000,000 times more energy leakage. Furthermore, energy leakage may increase exponentially with temperature in a transistor, and so keeping the operating temperature of graphene transistors low may be useful. According to embodiments of the disclosure, the one or more graphene-containing processor cores that are included in a graphene-containing chip multiprocessor are generally gated or otherwise disabled or placed in a reduced operation mode when an application with a high degree of instruction-level parallelism is being executed, where the degree of instruction-level parallelism of a software application may be generally considered as the number of operations that can be executed in a single clock cycle. The one or more graphene-containing processor cores may be used when execution of the application would benefit from substantially sequential execution. In this way, heating and leakage energy associated with the graphene-containing processor cores may be minimized while operating performance can be greatly increased for sequential execution.

FIG. 2shows a block diagram of an example embodiment of a chip multiprocessor (CMP)200, arranged in accordance with at least some embodiments of the present disclosure. CMP200may be a multi-core processor formed from a single integrated circuit die209and can be configured to carry out parallel processing tasks (e.g., processing multiple threads) using multiple processor cores formed on the die. For instance, CMP200may include a graphene-containing processor core201and two or more other processor cores202that include either no graphene-containing computing elements or relatively fewer graphene-containing computing elements than graphene-containing processor core201. In the embodiment illustrated inFIG. 2, CMP200includes a single graphene-containing processor core201and eight of the other processor cores202, however other combinations of graphene-containing processor core201and the other processor cores202may be formed on integrated circuit die209. As shown, CMP200may be physically and/or operatively coupled to a task manager250, a system clock230, and, in some embodiments, an operating system (OS)260. For clarity, additional shared resources included in CMP200that may be present on integrated circuit die209, such as L1 and L2 cache, I/O ports, bus interfaces, and the like, are omitted fromFIG. 2.

Graphene-containing processor core201may be any technically feasible processor or processor core that includes computing elements formed with graphene. These computing elements may include graphene-containing combinatorial elements, such as transistors, and/or graphene-containing sequential elements, such as flip-flops, among others. For example graphene-containing processor core201may include a specified percentage of graphene gates, e.g., transistors whose channel may be formed partially or entirely from graphene, and is therefore configured to execute software instructions or other computer-readable instructions much faster than the other processor cores202.

In some embodiments, substantially all computing elements of graphene-containing processor core201may be formed with graphene. In other embodiments, combinatorial elements in graphene-containing processor core201, such as transistors, may be formed with graphene. In yet other embodiments, specific computing elements of graphene-containing processor core201may be formed with graphene, with these computing elements being selected to improve performance of graphene-containing processor core201while minimizing or otherwise reducing leakage energy of graphene-containing processor core201. Such selected computing elements may include combinatorial elements, sequential elements, and/or a combination of both. Having fewer graphene-containing computing elements in graphene-containing processor core201may significantly reduce the leakage energy thereof, while having more graphene-containing computing elements may increase the performance thereof. Thus, in such embodiments, transistors and other computing elements that are generally used the most frequently in operation may be formed with graphene, and computing elements that are less frequently used may generally not be formed with graphene. For a particular integrated circuit configuration for graphene-containing processor core201, simulation software can be used during the design process to determine which computing elements are statistically the most- and least-used in graphene-containing processor core201.

Each of other processor cores202may be any technically feasible processor or processor core that includes no computing elements formed with graphene or otherwise fewer graphene-containing computing elements relative to graphene-containing processor core. The non-graphene computing elements may include combinatorial elements and/or sequential elements that are formed with semiconductor techniques and materials, such as silicon, gallium arsenide, and the like. Consequently, each of other processors202may be capable of operating at a significantly lower speed than graphene-containing processor core201, but can be used in parallel with one or more of the other processor cores202of integrated circuit209without incurring large (or with reduced) leakage energy.

Task manager250may be a scheduler module that can be configured to assign tasks to graphene-containing processor core201and the other processor cores202. As such, task manager250may also be responsible for gating, e.g., switching off power to, graphene-containing processor core201and/or to one or more of the other processor cores202. Task manager250may base such power gating on a currently determined degree of instruction-level parallelism in a software application being executed by CMP200, as well as or alternatively based on other factors. Specifically, when a high degree of instruction-level parallelism (referred to as “parallelism” hereinafter) is determined in such a software application, task manager250may be configured to gate graphene-containing processor core201and assign tasks associated with execution of the software application to an appropriate number of the other processor cores202. For example, when CMP200is executing a portion of the software application that includes substantial parallelism, such as parallel processing segment102inFIG. 1, task manager250may assign tasks to a plurality of the other processor cores202. Alternatively, when little or no parallelism is determined in the software application, task manager250may direct most or all tasks to graphene-containing processor core201for execution. For example, in instances in which no parallelism is determined, such as when executing computing thread115of sequential processing segment101inFIG. 1, all or substantially all tasks associated with the software application may be assigned to graphene-containing processor core201, thereby greatly enhancing performance of CMP200.

In some embodiments, the integrated circuit configuration, e.g., the arrangement of transistors, flip-flops, etc., of one or more of the other processor cores202may be substantially identical to the integrated circuit configuration of graphene-containing processor core201. In such embodiments, design and testing of CMP200can be greatly simplified. In other embodiments, all of the other processor cores202may be substantially identical to each other. In yet other embodiments, different groups of the other processor cores202may each have a common integrated circuit configuration, the integrated circuit configuration of each group being selected for optimal or otherwise improved processing of different applications or categories of applications. For example, one such group of the other processor cores202in CMP200may comprise graphics processing units (GPUs). In such embodiments, graphene-containing processor core201may have an integrated circuit configuration that is substantially identical to that of one particular group of the other processor cores202, except that the graphene-containing processor core201includes graphene-containing computing element(s) in its integrated circuit configuration.

In the embodiment illustrated inFIG. 2, task manager250is illustrated as a separate construct inFIG. 2. In other embodiments, the functions of task manager250may be distributed between OS260and CMP200, or may be implemented via circuitry formed on integrated circuit die209. It is noted that in some embodiments, since power gating in a chip multi-processor may generally not be performed with a physical switch, there may still be a finite but extremely small amount of leakage energy associated with processors or processor cores in CMP200that have been “gated” by task manager250.

System clock230may be either coupled to CMP200as shown inFIG. 2or integrated into CMP200as one or more components thereof. In some embodiments, graphene-containing processor core201may be clocked at a much higher frequency than other processor cores202. In other words, the other processor cores202may take several cycles to complete a computation while graphene-containing processor core201a single clock cycle of system clock230. In other embodiments, system clock230may include multiple clocking entities for providing suitable clock signals for each of graphene-containing processor core201and the other processor cores202of CMP200. Thus, in one embodiment, a higher-frequency clock signal may be provided to graphene-containing processor core201and a lower-frequency clock signal may be provided to the other processor cores202. In embodiments in which the other processor cores202include groups of processors or processor cores that each operates at a different clock frequency, a suitable clock signal may be provided to each group.

FIG. 3shows a block diagram of an example embodiment of a CMP300, arranged in accordance with at least some embodiments of the present disclosure. CMP300may be a multi-core processor formed from a single integrated circuit die309and may be substantially similar in configuration and operation to CMP200, except that CMP300may include multiple groups of graphene-based processor cores disposed on die309, where each group of processor cores includes processors configured to operate at a specified processor speed. Furthermore, each group of processor cores may have a different processor speed associated with the group than each of the other processor groups. In the embodiment illustrated inFIG. 3, CMP300includes a first group of ultra-fast processors301, a second group of fast processors302(having a processor speed that is slower relative to the first group), and a third group of slowest processors303(having a speed that is slower than the first and second groups). In other embodiments, CMP300may include more or fewer than three groups of graphene-containing processors, where each group of processor cores is configured to operate at a different speed.

The first group of ultra-fast processors301, the second group of fast processors302, and the third group of slowest processors303may each be configured to execute software instructions or other computer-readable instructions at a specified speed. In some embodiments, the specified clock cycle duration for each group may be a different integer multiple of the fastest group of graphene-containing processors. For example, in some embodiments, each of ultra-fast processors301may be configured with a relatively high percentage of graphene-containing computing elements, so that each of ultra-fast processors301can execute instructions at the highest clock frequency available in CMP300. In such embodiments, each of fast processors302may be configured with a lower percentage of graphene-containing computing elements than ultra-fast processors301, so that each of fast processors302can execute instructions using a specified clock cycle duration that is twice that of ultra-fast processors301. Thus, each of fast processors302may be configured to operate at a lower clock frequency than ultra-fast processors301. Similarly, each of slowest processors303may be configured with the lowest percentage of graphene-containing computing elements (in some embodiments this may be as low as 0% graphene-containing computing elements), so that each of ultra-fast processors301can execute instructions using a specified clock cycle duration that is three times that of ultra-fast processors301.

In operation, when CMP300executes instructions having relatively high parallelism, a suitable number of slowest processors303may be used, while fast processors302and ultra-fast processors301are power gated. When CMP300executes instructions that have little or no parallelism, a suitable number of ultra-fast processors301may be used, while fast processors302and slowest processors303are power gated. For example, when a substantially sequential portion of a software application is performed, the suitable number may one, so that a single ultra-fast processor301is used. When CMP300executes instructions that have moderate parallelism, a suitable number of fast processors302may be used, while all or most remaining processors in CMP may be power gated. In this way, the performance of CMP300can be optimized or otherwise improved for any specific work load. Specifically, the leakage energy of CMP300can be minimized or the effective processing speed of CMP maximized, depending on the nature, e.g., degree of parallelism, of instructions being executed by CMP300, as well as on one or more specified operational constraints.

In some embodiments, operational constraints used to optimize or otherwise improve performance of CMP300may include an allowable time delay, an energy budget for executing certain instructions, and a thermal budget for a processor or group of processors. For example, in video streaming applications or other multi-media applications, proper playback of videos and the like involve frames and sound that are provided to a user at specific intervals, and even the smallest delay in providing such content may seriously impact the viewing experience. Consequently, in some embodiments, an allowable time delay may be used in CMP300for determining which of first group of ultra-fast processors301, second group of fast processors302, and third group of slowest processors303are used to execute a specified portion of a software application. In such embodiments, CMP300can be configured to select processors for use so that specified instructions can be completed in less than an allowable time delay, such as a time associated with a frame rate of a video. In addition, CMP300can be further configured to select processors for use so that energy used by CMP300to execute the specified instructions, e.g., the combination of leakage energy and switching energy, is minimized or otherwise reduced. Thus, in such an embodiment, CMP300is configured to generally select the group of processors in CMP300that performs the applicable operations in the specified time with the lowest cost in energy. In other embodiments, for example when CMP300is associated with a mobile device in which energy usage is a concern, CMP300may be configured to select a group of processors that performs the applicable operations with the lowest cost in energy. In yet other embodiments, CMP300may be configured to select a group of processors based on a combination of time delay and energy cost. In other embodiments, CMP300may be configured to gate processors or groups of processors that have exceeded a thermal budget or a threshold temperature. Other configurations and/or combinations thereof are also possible. Methods of selecting groups of processors in a CMP based on an allowable time delay, a thermal budget, and/or an energy budget for executing specific instructions are described below in conjunction withFIGS. 4-7.

In some embodiments, ultra-fast processors301may be disposed on an edge of integrated circuit die309to facilitate heat loss. Because ultra-fast processors301generally include a higher percentage of graphene-containing computing elements than other processors in CMP300, ultra-fast processors301may generate significantly more heat when used to execute instructions. In some embodiments, ultra-fast processors301may be positioned at one or more corners of integrated circuit die309, as shown inFIG. 3, to further enhance heat loss during operation.

In some embodiments, overheating of ultra-fast processors301may be avoided by arranging low-leakage processor cores, such as slower processors303on integrated circuit die309such that none of ultra-fast processors301are disposed adjacent to any other of ultra-fast processor cores301. Because slower processors303generally include fewer or no graphene-containing computing elements, slower processors303may generate significantly less leakage energy than other processors in CMP300, and can be used to thermally isolate ultra-fast processors301from each other. In such embodiments, slower processors303may also be arranged to thermally isolate other high leakage energy processors, such as fast processors302, as shown inFIG. 3. It is noted that inFIG. 3, slower processors303are arranged on integrated circuit die309such that none of ultra-fast processors301or fast processors302are adjacent to each other. However, any other configurations of CMP300in which lower leakage energy processors are disposed between two or more processors having higher leakage energy also falls within the scope of this disclosure.

In some embodiments, execution of a sequential or substantially sequential portion of a software application, such as sequential processing segment101inFIG. 1, can be distributed between multiple graphene-containing, high-speed, high leakage energy processors in CMP300, such as ultra-fast processors301. As noted previously, the lack of parallelism in sequential processing segment101prevents more than one of ultra-fast processors301from executing the instruction of sequential processing segment101at one time. However, because any of ultra-fast processors301can execute sequential processing segment101with substantially equal speed, portions of sequential processing segment101can be executed sequentially by different ultra-fast processors301with little delay penalty. Thus, before the ultra-fast processor301that is executing sequential processing segment101reaches a non-ideal temperature and leakage energy, CMP300can switch execution of sequential processing segment101to another of ultra-fast processors301. In this way, sequential processing segment101can make up a relatively large portion of a software application and still be executed with the enhanced speed of a graphene-containing, high-speed, high leakage energy processor without overheating or non-ideal high leakage energy. In such embodiments, switching the execution of sequential processing segment101from one of ultra-fast processors301to another of ultra-fast processors301may be based on a measured or estimated temperature of the ultra-fast processor301currently executing sequential processing segment101. Alternatively, switching the execution of sequential processing segment101from one to another of ultra-fast processors301may be based on a time interval and therefore is performed repeatedly, such as periodically.

As noted above, in some embodiments, ultra-fast processors301, fast processors302, and slowest processors303may be defined by what percentage of graphene-containing computing elements are contained therein. In practice, however, the speed of a graphene-containing processor in CMP300may generally be an indirect function of the percentage of computing elements of the processor that are formed with graphene. This is because the computing elements in a particular processor may not all have the same utilization frequency. In other words, during typical operation of the processor, some paths of combinatorial and sequential elements in a processor may be used more than other paths. Since graphene-containing computing elements may typically contribute to the leakage energy of a processor even when disposed in an unused path of the processor, it is generally useful for the graphene-containing computing elements in the processor to have higher utilization than non-graphene computing elements. In this way, gains in processor performance are maximized relative to the additional leakage energy associated with the graphene-containing computing elements.

Because the percentage of computing elements in a processor that are formed with graphene may not be an accurate indicator of a processing speed of the processor, speed of a graphene-containing processor in CMP300may generally not be determined based solely on the percentage of computing elements. Instead, according to some embodiments of the disclosure, a processing speed of a graphene-containing processor in CMP300may be determined by running specific software applications using the graphene-containing processor of interest and directly measuring the performance of the processor. In other embodiments, a processing speed of a graphene-containing processor in CMP300may be estimated by performing simulations of the operation of the processor of interest in CMP300. The simulations may include the use of a benchmark application that mathematically approximates the coded instructions that may be executed by one or more processors of CMP300. Thus, the speed of ultra-fast processors301, fast processors302, and slowest processors303can be determined using simulations (or by measuring performance of actual processors), and appropriately adjusted in configuration so that CMP300can execute a software application with improved speed and energy leakage for the degree of parallelism associated with the software application.

As noted above, in some embodiments, CMP300may include multiple groups of processors or processor cores, where each group includes processors configured to operate at a specified processor speed. Consequently, CMP300may execute a software application and/or a portion of the software application in various ways, depending on which group of processors is used for execution. For example, for executing a portion of a software application having a relatively high degree of parallelism, CMP300may select the first group of ultra-fast processors301, the second group of fast processors302, or the third group of slowest processors303. The first group of ultra-fast processors301has the fastest processors in CMP300, but may not accommodate higher degrees of parallelism. In contrast, the third group of slowest processors303has the slowest processors in CMP300, but can accommodate higher degrees of parallelism. Generally, the third group of slowest processors303may be suited for executing portions of a software application with higher levels of parallelism, but in some instances, the higher speed of ultra-fast processors301may make the first group of ultra-fast processors301the relatively optimal selection in terms of aggregate speed of execution. Thus, in some embodiments, CMP300may be configured to select a group of processors to execute a portion of a software application based on the aggregate speed of execution of the group of processors as well as the level of parallelism associated with the portion of software application to be executed.

As noted above, CMP300can use a different group of processors to execute specific portions of a software application. Thus, a software application being executed by CMP300may be divided into distinct portions, such as blocks of code, where each block can be executed by a group of processors selected to perform with relatively optimal time delay and/or leakage energy. In some embodiments, a convex optimization procedure may be used to allocate execution of the different blocks of code to the different groups of processors in CMP300based on the degree of parallelism in each block of code and on the processing speed and leakage energy associated with each group of processors. In some embodiments, static scheduling may be used for such allocation and is described below in conjunction withFIGS. 4 and 5. In other embodiments, dynamic scheduling may be used for such allocation and is described below in conjunction withFIGS. 4 and 6.

FIG. 4is a diagram illustrating, according to one or more embodiments of the disclosure, an example dynamic programming process400for allocating execution of a software application between various groups of processor cores in a CMP. For example, dynamic programming process400may allocate execution of the software application or other computer-readable instructions between the first group of ultra-fast processors301, the second group of fast processors302, and the third group of slowest processors303in CMP300. The dynamic programming process illustrated inFIG. 4may be applied to either a static scheduling scheme or a dynamic scheduling scheme, each of which is described below.

Dynamic programming process400facilitates the execution of a software program using the various groups of processors in CMP300in a way that satisfies one or more specified operational constraints. For example, in executing a software program, dynamic programming process400can be used to minimize or otherwise reduce energy cost or time delay associated with executing the software program. Alternatively or additionally, dynamic programming process400can be used to minimize energy cost for executing the software application while completing the execution of the software program in less than a specified maximum time period. Moreover, dynamic programming process400can be used to satisfy one or more other operational constraints, in lieu of or in addition to time delay and energy cost.

In dynamic programming process400, a software application may be divided into multiple blocks, B1-Bm, which each includes non-overlapping portions of the code making up the software application. Each of blocks B1-Bmcan be executed by a different group of processors V1-Vnin a CMP, such as CMP300, where the various groups of processors are represented as nodes V1-VninFIG. 4. In CMP300, group of processors V1may correspond to the first group of ultra-fast processors301, group of processors V2may correspond to the second group of fast processors302, and group of processors Vnmay correspond to the third group of slowest processors303. In other embodiments, such as when a CMP includes 10 s or 100 s of processors or processor cores, n may be a relatively large number, for example 10, 20, or more. This is because such a CMP may be configured with 10, 20, or more different groups of processors, each group of the processors including processors having a percentage of graphene or a calculated processing speed that is unique with respect to the percentages of graphene or the calculated processing speeds associated with processors in the other groups of processors.

For example, for flexibility in the application of dynamic programming process400, group of processors V1may include a single ultra-fast processor that includes the highest percentage of graphene-containing computing elements and/or the shortest delay time in the CMP, group of processors V2may include two ultra-fast processors that each include the second highest percentage of graphene-containing computing elements and/or the second shortest delay time in the CMP, and so on. In some embodiments, the specified clock cycle duration for group of processors V2may be an integer multiple of the specified clock cycle duration for group of processors V1, for example 2. In such embodiments, the specified clock cycle duration for the other groups of processors, e.g., group of processors V3, group of processors Vn, etc., are each progressively higher integer multiples of the specified clock cycle duration for group of processors V1, for example, 3, 4, n, etc. Thus, for higher degrees of parallelism in blocks B1-Bm, a group of processors in the CMP may be selected that can take full advantage of the parallelism. In some embodiments, the progressively higher numbers of processors and/or clock cycle durations associated with group of processors V1-Vnmay increase by an integer value different than one, as described in the example above. Thus, the clock cycle duration for group of processors V2may be twice the clock cycle duration for group of processors V1, the clock cycle duration for group of processors V3may be four times the clock cycle duration for group of processors V1, the clock cycle duration for group of processors V4may be eight times the clock cycle duration for group of processors V1, and so on.

Dynamic programming process400may also include a starting node401, an ending node402, and a plurality of cost vectors O(1, 1/1)-O(m−1, n/n). Cost vectors O(1, 1/1)-O(m−1, n/n) each quantify a cost associated with context switching between two nodes, where “context switching” may refer to switching execution of a software application from a first node to a second node of dynamic programming process400. Generally, context switching may occur after the first node has completed execution of one of blocks B1-Bm-1and before the immediately following block is executed. Thus, in the notation for cost vectors O(j, k/l): m=the number of software blocks, n=the number of nodes (i.e., the number of different groups of processors), j=the completed block number, and therefore varies from 1 to m−1; k=the originating node (i.e., the group of processors that executed the completed block) and varies from 1 to n; and l=the target node (i.e., the group of processors to which execution of the software application is being switched) and varies from 1 to n. For example, cost vector O(3, ½) quantifies a cost associated with switching execution of a software program from originating node1(i.e., group of processors V1) to target node2(i.e., group of processors V2), the execution being switched after block B3has been completed by originating node1and prior to execution of block B4.

In some embodiments, cost vectors O(1, 1/1)-O(m−1, n/n) may each quantify a time delay cost associated with switching execution from an originating node to a target node. In other embodiments, cost vectors O(1, 1/1)-O(m−1, n/n) may each quantify an energy cost associated with switching execution from the originating node to the target node. In a particular embodiment, cost vectors O(1, 1/1)-O(m−1, n/n) may each quantify both a time delay cost and an energy cost associated with switching execution from the originating node to the target node. Generally, the value of each of cost vectors O(1, 1/1)-O(m−1, n/n) may be proportional to the time and/or energy cost associated with sending data from the originating node to the target node. Of course, when no context switching takes place between the execution of a first block and a second block, e.g., the same group of processors executes both the first block and the second block, the value of the cost vector may be zero. Stated in cost vector notation, the value of any cost vector in which k=l is zero.

Dynamic programming process400may use cost vectors O(1, 1/1)-O(m−1, n/n) and execution costs associated with each group of processors V1-Vnto execute each block of the software application to quantify time delay cost and energy cost for each possible execution path from starting node401to ending node402. Then, dynamic programming process400may select an optimal path from starting node401to ending node402, specifying which group of processors V1-Vnof a CMP executes each of blocks B1-Bm. Such a path inFIG. 4may be selected by dynamic programming process400to satisfy one or more operational constraints, such as a minimum time delay, a minimum energy cost, and the like.

In some embodiments, such as in video related applications, dynamic programming process400may select a path in which an allowable time delay is not exceeded in executing a software application, or, in some embodiments, a specific portion or subroutine of the software application. In such embodiments, dynamic programming process400may be further configured to select a path that also minimizes energy expenditure without exceeding the allowable time delay. In other embodiments, for example in computing devices in which energy budget is not an issue, dynamic programming process400may be configured to select a path that minimizes time delay regardless of energy budget. In such embodiments, dynamic programming process400may further include a measured or predicted temperature of the processors in the CMP to further eliminate some possible execution paths. For example, context switching costs can be avoided by using the same group of processors in a CMP for all or most blocks of a software application, therefore many low energy-expenditure execution paths may include little or no context switching. However, because most or all of groups of processors V1-Vnmay include graphene-containing computing elements, overheating can occur if the graphene-containing computing elements are used for extended periods of time. Consequently, dynamic programming process400may also include an allowable processor temperature as an operational constraint when selecting an optimal execution path.

In operation, dynamic programming process400may first calculate an execution cost for each group of processors V1-Vnto execute block B1of a software application as well as all cost vectors O(1, 1/1)-O(m−1, n/n). These cost vectors may quantify context switching costs, after execution of block B1, from each group of processors V1-Vnto each other group of processors V1-Vn. Dynamic programming process400may then store the calculated execution costs and cost vectors O(1, 1/1)-O(m−1, n/n). In some embodiments, dynamic programming process400may store particular combinations, e.g., the combinations of execution cost and cost vector that have less than a particular desired time and/or energy cost. In such embodiments, elimination of inferior, e.g., high cost, combinations can greatly reduce the complexity and number of calculations required for dynamic programming process400to provide an optimal solution. As noted above, in some embodiments, estimated processor temperatures may also be calculated as part of dynamic programming process400, which can further point out combinations that can be considered inferior due to non-ideal processor temperatures. Furthermore, other operational constraints may be calculated and used to determine inferior combinations that are not stored.

After storage of the execution cost/cost vector combinations, dynamic programming process400may then repeat the above process for the next block B2of the software application. In embodiments in which inferior combinations are not stored for the previous block, in this case block B1, all possible combinations of execution costs for each of processors V1-Vnand cost vectors O(2, 1/1)-O(2, n/n) may generally not be calculated. This is because the exclusion of inferior combinations may eliminate some possible combinations for execution of block B2. For example, when all cost vectors associated with switching context to a particular group of processors, for example group of processors V3, are included in inferior combinations, there may be no need to calculate any combinations that include group of processors V3for the next block, in this case block B2. This process may then repeat for each remaining block of the software application.

Given the non-inferior combinations described above, dynamic programming process400can then determine an optimal path in terms of a specified operational constraint, such as time delay, energy delay, time delay-energy delay product, etc. Generally the solution of such a problem may be an optimization problem with a running time that is quadratic, and can be readily solved by one of ordinary skill in the art having the benefit of this disclosure.

In some embodiments, dynamic programming process400may be applied to a static scheduling scheme. For example, dynamic programming process400may be performed by task manager250inFIG. 2. In such embodiments, an optimal path for the execution of a software application in a CMP may be determined at compilation time. Because of this compilation-time implementation, substantially all information needed for optimization may be known when dynamic programming process400is used to determine an optimal path for executing a software application: the instruction-level parallelism of each block, estimated execution cost for blocks B1-Bmby each group of processors V1-Vn, each of cost vectors O(1, 1/1)-O(m−1, n/n), etc. Consequently, an optimal path can be found in a substantially deterministic fashion. However, the application of dynamic programming process400for determining such an optimal path may add some time and energy delay to the process of executing the software application, since the process of compiling the software application can be made more complex and time-consuming and generally is completed prior to execution of the software application.

FIG. 5sets forth a flowchart of an example method500for scheduling instructions for processing by a chip multiprocessor having multiple groups of processor cores, according to an embodiment of the disclosure. Method500may include one or more operations, functions or actions as illustrated by one or more of blocks501,502,503, and/or504. Although the blocks are illustrated in a sequential order, these blocks may also be performed in parallel, and/or in a different order than those described herein. Also, the various blocks may be combined into fewer blocks, divided into additional blocks, and/or eliminated based upon the desired implementation. Additional blocks representing other operations, functions or actions may be provided in other embodiments. Although method500is described in conjunction with CMP200ofFIG. 2and CMP300ofFIG. 3, other CMPs may be configured to perform method500.

Method500may begin in block501“determine time cost and/or energy cost for processing first block of instructions.” Block501may be followed by block502“determine time cost and/or energy cost for processing second block of instructions,” block502may be followed by block503“determine context switching costs,” and block503may be followed by block504“select a processor group to execute first block of instructions and a processor group to execute second block of instructions.”

In some embodiments, prior to block501, a task manager or other instruction-scheduling entity associated with a CMP, such as task manager250inFIG. 2, may separate a software application into sequential blocks, such as blocks B1-BminFIG. 4. In other embodiments, such blocks may already be defined in the software application.

In block501, the task manager or other instruction-scheduling entity associated with the CMP determines at least one of a time cost (e.g., a time delay), an energy cost (e.g., a particular energy expenditure), a thermal cost (e.g., an estimated processor temperature increase) and/or other cost(s) for each of the multiple processor groups in the CMP to execute a first block of instructions from an application. Generally, and as described above in conjunction withFIG. 3, in a given one of the multiple processor groups, all processors may have a substantially equal percentage of graphene-containing computing elements. Furthermore, a different percentage of graphene-containing computing elements may be associated with each group, e.g., for each of the multiple processor groups, a percentage of graphene-containing computing elements associated with the processor group may be different than a percentage of graphene-containing computing elements associated with any other of the multiple processor groups.

In block502, the task manager or other instruction-scheduling entity determines at least one of a time cost, an energy cost, a thermal cost and/or other cost(s) for each of the multiple processor groups to execute a second block of instructions from the application.

In block503, the task manager or other instruction-scheduling entity determines context switching costs associated with switching execution of the application from any one of the multiple processor groups to any other of the multiple processor groups. In method500, the context switching may take place after the first block of instructions is executed by a first of the multiple processor groups and before the second block of instructions is executed by a second of the multiple processor groups. Generally, blocks502and503may be repeated for all remaining blocks of the software application, so that all or most possible context switching costs may be considered as well as all or most time, energy, and/or thermal costs associated with each of the multiple processor groups executing each block of the software application.

In block504, the task manager or other instruction-scheduling entity selects one of the multiple processor groups to execute the first block of instructions and one of the multiple processor groups to execute the second block of instructions. Generally, the selecting entity may also select which of the multiple processor groups executes each of the remaining blocks of instructions of the software application, thereby determining an optimal execution path by which the CMP can execute the software application. The selections made in block504may be based on the time, energy, and/or thermal costs determined in blocks501and502, and on the context switching costs determined in block503. Generally, given the information determined in blocks501-503, the solution of such a problem is a standard optimization problem.

It is noted that method500can be configured as a static scheduling scheme. Consequently, in some embodiments, method500may be performed during compilation of the software application.

In some embodiments, dynamic programming process400may be applied to a dynamic scheduling scheme and may be performed by task manager250inFIG. 2or any other instruction-scheduling entity associated with a particular CMP. In such embodiments, an optimal path for the execution of a software application in the CMP may not be determined at compilation time. Instead, optimal instruction scheduling may be determined for one block of a software application during execution of the software application, e.g., while the immediately preceding block of the software application is being executed. In this way, the CMP may not experience the time, energy and/or thermal costs associated with an expanded and more complex compilation process. For example, while block B1inFIG. 4is being executed by one of the groups of processors V1-Vn, the next group of processors may be selected that is optimal for executing block B2.

Furthermore, scheduling of instructions for the software application using such a dynamic scheduling scheme can be much more adaptive than a static scheduling scheme. Specifically, scheduling of each block of instructions of the software application may be modified based on the actual execution of the software application, whereas in static scheduling, certain assumptions may be generally made regarding instruction-level parallelism of each block of the software application based on a statistical analysis of each block of instructions and other information. Therefore, in a dynamic scheduling scheme, the actual degree of instruction-level parallelism present in the software application can be taken into account when scheduling the next block of instructions: whenever some operations are not scheduled during one clock cycle, execution in the next clock cycle can be switched to a group of processors that can handle more operations; whenever processors in the current active group of processors includes one or more unused processors, execution in the next clock cycle can be switched to a group of processors that includes fewer processors. In comparison, in a static scheduling scheme, optimal scheduling for all blocks of instructions may be determined at one time, but may be based in part on estimated parallelism.

It is noted that, because each operation of dynamic scheduling generally may be made very quickly, for example in a single clock cycle, a highly optimized solution may not be determined. Unlike in static scheduling schemes, all possible execution paths via all processor groups and cost vectors may not be quantified and compared for all software blocks. Instead, the execution costs and context switching costs for a very limited number of blocks, typically the next block, can be calculated and considered in the time available.

FIG. 6sets forth a flowchart summarizing an example method600for scheduling instructions for processing by a chip multiprocessor that includes graphene-containing computing elements, according to an embodiment of the disclosure. Method600may include one or more operations, functions, or actions as illustrated by one or more of blocks601,602,603, and/or604. Although the blocks are illustrated in a sequential order, these blocks may also be performed in parallel, and/or in a different order than those described herein. Also, the various blocks may be combined into fewer blocks, divided into additional blocks, and/or eliminated based upon the desired implementation. Additional blocks representing other operations, functions or actions may be provided in other embodiments. Although method600is described in conjunction with CMP200ofFIG. 2and CMP300ofFIG. 3, other CMPs may be configured to perform method600.

Method600may begin in block601“determine time cost and/or energy cost for processing first block of instructions.” Block601may be followed by block602“selecting a first of the multiple processor groups to execute first block of instructions,” block602may be followed by block603“determine time cost and/or energy cost for processing second block of instructions,” and block603may be followed by block604“select a second of the multiple processor groups to execute second block of instructions.”

In some embodiments, prior to block601, a task manager, such as task manager250inFIG. 2, or other instruction-scheduling entity associated with a CMP may separate a software application into sequential blocks, such as blocks B1-BminFIG. 4. In other embodiments, such blocks may already be defined in the software application.

In block601, the task manager or other instruction-scheduling entity associated with the CMP determines at least one of a time cost, an energy cost, a thermal cost and/or other cost(s) for each of the multiple processor groups to execute a first block of instructions from the software application.

In block602, the task manager or other instruction-scheduling entity selects a first of the multiple processor groups to execute the first block of instructions. Generally, the selection is based on at least one of the determined time, energy cost, thermal cost, and/or other cost(s) determined in block602.

In block603, the task manager or other instruction-scheduling entity determines at least one of a time cost, an energy cost, a thermal cost and/or other cost(s) for each of the multiple processor groups to execute a second block of instructions from the application. The second block of instructions generally may be the block of instructions immediately following the first block of instructions referenced in blocks601and602. In some embodiments, the task manager or other instruction-scheduling entity may also determine context switching costs in block603, such as cost vectors O(1, 1/1)-O(1, n/n) inFIG. 4.

In block604, the task manager or other instruction-scheduling entity selects a second of the multiple processor groups to execute the second block of instructions, where the selection of the second of the multiple processor groups may be performed after the first of the multiple processor groups has begun execution of the first block of instructions. In other words, block604generally may take place concurrently with the execution of the first block of instructions by the first of the multiple processor groups. It is noted that the first of the multiple processor groups and the second of the multiple processor groups may be the same processor group, such as when the number of processors in the currently active processor group is matched to the degree of parallelism in the currently executing block of instructions. In some embodiments, the selection may also be based on context switching costs determined in block603. Generally, the procedures of blocks603and604may be continued until all blocks in the software application are executed.

The selection of the second of the multiple processor groups made in block604may be based on a level of parallelism of the application being run on the chip multiprocessor while the first of the multiple processor executes the first block of instructions. For example, when one or more operations associated with the first block of instructions are not scheduled when the first block of instructions is being executed by the first of the multiple processor groups, the second of the multiple processor groups may be a processor group having more processors than the first of the multiple processor groups. In this way, the parallelism in executing the next block of instructions, e.g., the second block of instructions, expanded to take full advantage of the degree of parallelism currently present in the software application. Alternatively or additionally, when one or more processors in the first of the multiple processor groups includes one or more unused processors, the second of the multiple processor groups may be a processor group having fewer processors than the first of the multiple processor groups. In this way, faster processors may be used to execute the next block of instructions.

For example, if the supply voltage for a CMP is increased, the overall delay for the CMP may be reduced, while both switching and leakage energy increase. Or, if the threshold voltage is increased, the overall delay may also be increased, while both switching and leakage energy may be reduced.

The above-referenced techniques may be orthogonal to embodiments described herein and, in some embodiments, may be used in conjunction with one or more embodiments for increased effectiveness. In addition, some optimization techniques such as dynamic programming may be directly applicable with minimal modification to the delay and energy costs.

FIG. 7is a block diagram of an illustrative embodiment of a computer program product700for implementing a method for scheduling instructions for processing by a CMP that includes graphene-containing computing elements arranged in multiple processor groups. Computer program product700may include a signal bearing medium704. Signal bearing medium704may include one or more sets of executable instructions702that, when executed by, for example, a processor of a computing device, may provide at least the functionality described above with respect toFIGS. 2-6.

In some implementations, signal bearing medium704may encompass a non-transitory computer readable medium708, such as, but not limited to, a hard disk drive, a Compact Disc (CD), a Digital Video Disk (DVD), a digital tape, memory, etc. In some implementations, signal bearing medium704may encompass a recordable medium710, such as, but not limited to, memory, read/write (R/W) CDs, R/W DVDs, etc. In some implementations, signal bearing medium704may encompass a communications medium706, such as, but not limited to, a digital and/or an analog communication medium (e.g., a fiber optic cable, a waveguide, a wired communications link, a wireless communication link, etc.). Computer program product700may be recorded on non-transitory computer readable medium708or another similar recordable medium710.

FIG. 8is a block diagram illustrating an example computing device800that is arranged for managing programmable logic circuits in a chip multiprocessor, in accordance with at least some embodiments of the present disclosure. In a very basic configuration802, computing device800typically includes one or more processors804and a system memory806. A memory bus808may be used for communicating between processor804and system memory806.

Depending on the desired configuration, processor804may be of any type including but not limited to a microprocessor (μP), a microcontroller (μC), a digital signal processor (DSP), or any combination thereof. Processor804may include one more levels of caching, such as a level one cache810and a level two cache812, a processor core814, and registers816. An example processor core814may include an arithmetic logic unit (ALU), a floating point unit (FPU), a digital signal processing core (DSP Core), or any combination thereof. Processor804may include programmable logic circuits, such as, without limitation, FPGA, patchable ASIC, CPLD, and others. Processor804may be similar to CMP200or inFIG. 2or CMP300inFIG. 3. An example memory controller818may also be used with processor804, or in some implementations memory controller818may be an internal part of processor804.

Depending on the desired configuration, system memory806may be of any type including but not limited to volatile memory (such as RAM), non-volatile memory (such as ROM, flash memory, etc.) or any combination thereof. System memory806may include an operating system820, one or more applications822, and program data824. Application822may include one or more applications separated into blocks, as described above in conjunction withFIG. 4. Program data824may include data that may be useful for operation of computing device800. In some embodiments, application822may be arranged to operate with program data824on operating system820. This described basic configuration802is illustrated inFIG. 8by those components within the inner dashed line.

Computing device800may have additional features or functionality, and additional interfaces to facilitate communications between basic configuration802and any required devices and interfaces. For example, a bus/interface controller890may be used to facilitate communications between basic configuration802and one or more data storage devices892via a storage interface bus894. Data storage devices892may be removable storage devices896, non-removable storage devices898, or a combination thereof. Examples of removable storage and non-removable storage devices include magnetic disk devices such as flexible disk drives and hard-disk drives (HDD), optical disk drives such as compact disk (CD) drives or digital versatile disk (DVD) drives, solid state drives (SSD), and tape drives to name a few. Example computer storage media may include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data.

System memory806, removable storage devices896and non-removable storage devices898are examples of computer storage media. Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which may be used to store the desired information and which may be accessed by computing device800. Any such computer storage media may be part of computing device800.

Computing device800may also include an interface bus840for facilitating communication from various interface devices (e.g., output devices842, peripheral interfaces844, and communication devices846) to basic configuration802via bus/interface controller830. Example output devices842include a graphics processing unit848and an audio processing unit850, which may be configured to communicate to various external devices such as a display or speakers via one or more A/V ports852. Example peripheral interfaces844include a serial interface controller854or a parallel interface controller856, which may be configured to communicate with external devices such as input devices (e.g., keyboard, mouse, pen, voice input device, touch input device, etc.) or other peripheral devices (e.g., printer, scanner, etc.) via one or more I/O ports858. An example communication device846includes a network controller860, which may be arranged to facilitate communications with one or more other computing devices862over a network communication link, such as, without limitation, optical fiber, Long Term Evolution (LTE), 3G, WiMax, via one or more communication ports864.

Embodiments of the present disclosure enable the use of processors that include graphene-containing computing elements while minimizing or otherwise reducing the effects of high leakage energy associated with graphene computing elements. Furthermore, embodiments of the present disclosure provide systems and methods for scheduling instructions for processing by a CMP that includes graphene-containing computing elements arranged in multiple processor groups.