CN102934081B - Operation space method, system and apparatus - Google Patents

Abstract

The present invention, referred to as a runtime space, relates to the field of computing system management, data processing and data communications, and in particular to a collaborative method and system that provides economical computing, particularly for decomposable multi-component tasks that can be executed on multiple processing elements, by using a metric space representation of code and data locality to guide the allocation and migration of code and data, by performing analytics to identify code regions that provide improved runtime opportunities, and by providing a low-power, local, secure memory management system adapted to distribute calls to compressed code segments that access local memory. The runtime space provides a mechanism to support hierarchical allocation, optimization, monitoring, and control, and to support resilient, energy efficient, large-scale computing.

Description

Operation space method, system and apparatus

inventor:

Rishi L. Khan

Related applications

This application claims the benefit of the following applications:

[1] U.S. Provisional Application No. 61/323,362, filed April 13, 2010.

[2] U.S. Provisional Application No. 61/377,067, filed August 25, 2010.

[3] U.S. Provisional Application No. 61/386,472, filed September 25, 2010.

Each of the above applications is incorporated herein by reference in its entirety.

technical field

The present invention, referred to as a runspace, relates generally to the fields of computing system control, data processing, and data communications, and in particular to methods and systems for providing economical computing, including execution of large multi-components distributed over multiple processing elements Task.

Background of the invention

Modern high-end computer architectures contain thousands or even millions of processing elements, large amounts of distributed memory, and various levels of non-local memory, network components, and storage infrastructure. These systems present great challenges for performing static and dynamic optimization of resources consumed by applications. Traditionally, computer architectures have struggled to provide applications with only a single, simple address space, and to provide inherently reasonable semantics for subsequent code execution and data access. The resulting paradigm has worked well for many years, but prevents optimal resource allocation when computing and data are distributed through parallel processing rather than through faster clock rates and virtually all hardware acceleration is achieved. The present invention anticipates the stage at which semiconductor manufacturers are addressing the physical or cost-effective constraints of reducing circuit size, considering parallelism to be the most promising avenue for performance improvement. In applications where maximum performance is critical, traditional OS resource allocation through interrupts and preemption has hampered performance. Therefore, the main challenge in enabling efficient distributed computing is to provide system software that makes optimal use of the physical system, while at the same time providing a usable abstract model of computation to the application coder.

Contents of the invention

The present invention provides systems and methods for compiling and running computer programs to achieve the goal of seeking the most economical program execution. These systems and methods involve: at compile time, determining an optimal efficiency execution environment for a given program segment called a codelet; and at run time, accordingly placing and scheduling the codelet into its optimal efficiency execution environment for execution.

Embodiments of the present invention include methods for efficiently allocating data processing system resources to application tasks. The method involves: obtaining a set of codelets that implement certain data processing tasks; determining dependencies among these codelets; and based on the dependencies among the codelets and based on the availability of data processing system resources and the relative use of the various resources Cost, dynamically places and schedules codelets for execution on a given data processing system using identified resources.

According to an embodiment of the present invention, the method for seeking user- or system-defined goals for executing a computer program is based on decomposing a given computer program into a set of abstract models including codelets, sets of cooperating codelets, cooperating abstract models Sets and data shared between members of a given abstract model. Furthermore, in various embodiments, the methods include the steps of: obtaining program run-time information associated with the program regarding abstraction models, performance, and resource utilization; and using the program run-time information to direct the computer program or portion of a computer program Subsequent placement or execution scheduling of ongoing or subsequent in-run abstract models. Additional embodiments of these methods include the steps performed at least in part by the run-time system: defining memory space or proximity objects for members of the abstract model in execution time; initially placing data and scheduling execution of codelets in the abstract model, and, when seeking to Migrate members of an abstract model when it is beneficial to specify user- or system-defined goals, where placement and migration are performed in a coordinated manner to maximize actual proximity among members of the abstract model according to their defined goals.

Other aspects of the invention include a method for optimally parallelizing the execution of a software program, the method involving the steps of: a) querying the runtime system to find the number of processing cores available to execute the program; b) determining the program the maximum number of processing units that can be divided into; c) divide the program into an optimal number and size of processing units, such as codelets, based on the quantities determined in steps a) and b); and d) according to each step c) Division, parallel execution of management procedures.

According to an embodiment of the present invention, the system optimally locates and schedules the execution of a set of codelets on a given data processing hardware. These systems include digital hardware and software based components for: exchanging information between sets of processing resources related to metrics related to optimal placement of sets of codelets between processing resources; on which of the processing resources the codelet to be executed is located; and using the processing resource to place and schedule execution of the codelet based on said determination, wherein at least some of said components are dynamically employed during system runtime. A further aspect of the invention relates to a data processing system comprised of multiple cores, wherein the system includes: a) a set of system management agents, the set including one or more of the following: data percolation manager, codelet scheduler manager, codelet migration manager, load balancer, power tuner, or performance manager; and b) components for said set of agents to change in a cooperative fashion to seek system-wide goals, in various ways that provide dynamic runtime system behavior In embodiments, the target is time-varying.

The invention also encompasses application and system software programs in various combinations for carrying out the methods of the invention, as well as hardware systems and related hardware and software products for running these programs.

Description of drawings

FIG. 1 shows an exemplary operating space structure.

Figure 2 illustrates an exemplary runspace allocation with multiple ranges.

Figure 3 illustrates an exemplary runspace runtime system.

Figure 4 shows an exemplary case of runtime performance monitoring and allocation.

Figure 5 illustrates the runtime behavior of code in the runspace system.

Figure 6 illustrates an exemplary interaction hierarchy.

Figure 7 illustrates an exemplary self-optimizing operating system.

Figure 8 illustrates explicit and implicit apply instructions.

Figure 9 illustrates an exemplary micro memory management unit.

Figure 10 illustrates an exemplary application use case.

Figure 11 shows an exemplary grouping of runspaces over time.

Figure 12 shows a computing system using codelets.

Fig. 13 shows a codelet set representation system.

Figure 14 shows an example of codelet conversion.

Figure 15 shows the meta-level codelet set distribution.

Figure 16 illustrates codelet set execution and migration.

Figure 17 shows the double-ended queue concurrent access mechanism: write/enqueue.

Figure 18 shows the dequeue concurrent access mechanism: read/dequeue.

Figure 19 shows concurrent access to an array (A) by atomic addition: write.

Figure 20 shows concurrent access to array (B) by atomic addition: write.

Figure 21 shows concurrent access to array (C) by atomic addition: read.

Figure 22 shows a linked list, specifically an atomic addition array (A).

Figure 23 shows a linked list, specifically an atomic addition array (B).

Figure 24 shows a linked list, specifically an atomic addition array (C).

Fig. 25 shows a linked list, specifically an atomic addition array (D).

Figure 26 shows a linked list, specifically an atomic addition array (E).

Figure 27 shows concurrent access through a shared array with steering.

Figure 28 shows combined network distribution increments.

Figure 29 shows single-task and multi-task execution concurrent access by atomic addition array (A).

Figure 30 shows single-task and multi-task execution concurrent access by atomic addition array (B).

Figure 31 shows single-task and multi-task execution concurrent access by atomic addition array (C).

Figure 32 shows single-task and multi-task execution concurrent access by atomic addition array (D).

Figure 33 shows single-task and multi-task execution concurrent access by atomic addition array (E).

Fig. 34 shows a scenario of a codelet computing system.

Figure 35 shows a general exemplary structure at the chip level.

Figure 36 shows the board-level/system-level general structure.

Figure 37 shows the assignment of codelets and codelet sets

Figure 38 shows the double buffer calculation (A).

Figure 39 shows the double buffer calculation (B).

Figure 40 shows the double buffer calculation (C).

Figure 41 shows the double buffer calculation (D).

Figure 42 shows the double buffer calculation (E).

Figure 43 shows the double buffer calculation (F).

Figure 44 shows the double buffer calculation (G).

Figure 45 shows matrix multiplication with SRAM and DRAM.

Figure 46 shows matrix multiplication double buffering/DRAM.

Fig. 47 shows an example of calculating LINPACK DTRSM (linear algebra function).

Figure 48 shows run-time initialization of a codelet set for the DTRSM case.

Fig. 49 shows an example of quick sort.

Figure 50 shows an extensible system function with an application codelet set.

Figure 51 illustrates the conversion of legacy code to multitasking.

Figure 52 shows the black box code running with the multitasking code.

Figure 53 shows the improved black box code running with the multitasking code.

detailed description

Glossary of terms used in this invention

Application: A set of instructions containing a single or multiple related specific tasks that the user wishes to perform

Application Programming Interface (API): The set of programmer-accessible assemblies that expose system functionality to programs written by application developers who may not have access to internal components of the system, or may wish to obtain A simpler or more consistent interface is obtained for the basic functionality of the interface, or it may be desired to obtain an interface that conforms to a specific standard for interoperability.

• Codelet: A set of instructions that, after their input is available, can be executed substantially continuously to completion.

• Codelet Set: A group of codelets that can be processed as a unit with respect to dependency analysis or execution.

• Computational Area: A set of processing elements grouped by locality or function. These areas may hierarchically include other computing areas. Hierarchical region instances may include systems, nodes, sockets, cores, and/or hardware threads.

• Concurrent system: the set of concurrent processes and the set of objects manipulated by those processes.

• Core: The processing unit of a computing device. These processing units include, but are not limited to, CPUs (Central Processing Units), GPUs (Graphics Processing Units), FPGAs (Field Programmable Arrays), or subsets of the foregoing.

• Dependency: A directed arc between two codelet sets that indicates that one codelet set ends before the other begins.

• Fractal Adjustment Architecture: A mechanism that safely and reliably provides efficient use of resources at multiple scales in the system, where similar strategies are used at each level.

GACT/Generalized Role: A user or a group of users, or a group of users and software agents, or a computing entity that acts as a user to achieve a certain goal.

• GCS/Generalized Computing System: One or more computers including programmable processors, memory, I/O devices that provide data access and computing services.

• CSIG/codelet signal: A communication between codelets or between a monitoring system and at least one codelet that enables a codelet whose dependencies are satisfied or conveys status and completion information.

• Hierarchical Execution Model: A multi-level execution model in which applications are decomposed at several levels, including codelets at the base level of granularity.

• Linearizable: One or more operations that appear to occur simultaneously in a concurrent processing system. Linearizability is usually achieved by sequential (as a group) or deleted (wrap-back recovery) instructions, and by systems that provide "atomic" operations through specific instructions or locks around critical regions.

· Lock-free synchronization: non-blocking synchronization of shared resources to ensure (at least) system-wide progress.

• Local Area Network (LAN): Connects computers and other network devices over relatively small distances, usually within a single organization.

• Node: A device consisting of one or more computer processors, and optionally memory, network interfaces, and peripherals.

• Overprovisioning: Provisioning more than a minimum number of processing elements and local memory to allow greater margin for resource allocation. For example, replacing a small number of processing elements running highly sequential tasks at high clock rates with more processing elements running more distributed code and data at low clock rates.

• Multitasking: A set of related tasks that can be processed as a unit with respect to a set of computing resources. Typically, multiple tasks have similar resource requirements and may seek allocation of a batch of resources. Multitasking can also have complementary resource requirements, and load balancing can be performed by means of distributed requests.

• Proximity: such as locality in memory space, computation space, or states that are close in time or dependencies.

Queue: A data structure that accepts enqueued elements and deletes and returns dequeued elements. Elements can be enqueued or dequeued at any position, including but not limited to the beginning, end, or middle of the queue.

• Run Time System (RTS): A collection of software designed to support the execution of computer programs.

• Scalability: The capability of a computer system, structure, network, or process that allows it to efficiently meet the needs of greater processing volumes by using additional processors, memory, and connectivity.

• Self-aware control system: A system that uses a model of its own properties and constraints, allowing high-level goals to be expressed declaratively with respect to model properties.

• Signals: Events that enable codelet sets. During execution, signals can be emitted by codelets.

• Task: A unit of work in a software program.

• Thread: A long-lived run-time processing object that is restricted to a specific processing element.

· Wait-free synchronization: Guarantees non-blocking synchronization of shared resources with system-wide progress and per-thread progress.

Wide Area Network (WAN): Connects computers and other network devices over a potentially large geographic area.

The present invention provides methods and systems for representing, manipulating and executing codelet sets. A codelet is a generally non-preemptive group of instructions that, after their dependencies are satisfied, typically continue to execute to completion. A codelet set is a group of codelets that can be processed as a unit with respect to dependency analysis or execution. Codelet sets differ from traditional programming and execution models in significant ways. Applications are broken down into independent code segments that can be executed with a minimal amount of system coordination required. According to embodiments of the present invention, instead of centralized control and resource allocation, the system code (which itself is implemented by the codelet set) only initializes the platform of the codelet set to run by enabling the initial codelets of the codelet set. These codelets have no a priori dependencies, so they are enabled once the codelet set is enabled. Codelet applications do not have to remain entirely literal code spaces during their execution. In fact, conversion of some infrequently used codelet set elements may be deferred, if indeterminately, if they are not needed for particular data provided during a particular run or execution.

Features of embodiments of the codelet set method include:

Decompose computational tasks into abstract models that minimize inter-model dependencies;

The structure of the abstract dependency map that directs the initial codelet enablement and initial and ongoing allocation of computing resources;

Use computational representations with at least the same expressive power as Petri networks;

Migrating sets of executing or soon-to-be-executed codelets to take advantage of locality of resources such as local memory, specific data and intermediate results, and locality of cooperating codelets to minimize communication latency;

· Migrating codelet sets to obtain a better global allocation of resources to allow attenuation of some processing resources to save energy or preserve capacity, or to utilize resources more suitable for a given processing task, such as in heterogeneous systems;

use of multitasking, i.e. relative tasks that can be processed as a unit with respect to a set of computing resources or can be managed by a presentation agent task that acts to acquire the required resource or additional tasks of the group;

Use of atomic addition arrays that efficiently mediate concurrent access of codelets working on shared data or other processing inputs or resources, where the order of access is potentially important;

·Use linked list atomic addition array, which allows dominant local access efficiency while supporting virtually unlimited growth of concurrent data storage;

Use of multi-turn/multi-generation atomic-add arrays to maintain the benefits of strict local storage while supporting a large number of pending operations; and

• Combine networks to provide cascaded delta-to-memory accesses, avoiding the bottleneck of a single global next function.

Key concepts and aspects of the present invention are described below with reference to the accompanying drawings. Note that in the following description, the steps and order of steps are given for illustrative purposes, but many other orders, subsets and supersets will be apparent to practitioners after describing the invention. The purpose of brevity prevents listing every combination of steps falling within the legal scope of the invention.

Summary:

Runspaces are structured to take advantage of the highly parallel architecture of many processing elements, where both data and code are distributed in a coherent multi-level organization. Runspace systems and methods achieve optimal use of processing resources by maintaining a metric space model in which distance measures are applied to code and data. A good level of task allocation is the level of codelets, which are groups of instructions that can be non-preemptively executed to completion after input conditions are met.

In an embodiment of the present invention, the runspace method and system allocate computing resources to computing tasks by performing one or more of the following steps: obtaining a set of small codes that implement a task set; obtaining a set of data specifications requested by a small code; Code locality and the metric space of the data they will access; obtain a statically defined initial arrangement of codelets relative to the distance of the metric space; use a metric space representation to initially place codelets or data; obtain dynamically available runtime resources for codelets and data requests; and using the metric space representation to dynamically place or move codelets or data.

Additionally, in an embodiment, the runspace prepares for allocation opportunities and utilizes these opportunities at runtime by, at compile time, analyzing underlying code and data for manipulation and references indicating opportunities to merge or migrate codelets and data allocation; and then perform runtime migrations of these codelets, merged codelets, or data to practice the opportunities presented by actual code and data allocation.

Additionally, to support fine-grained execution of codelets, implementations of the runspace provide safe and efficient local memory access by doing one or more of the following actions: breaking application code into codelets; providing local routing with logical and physical addresses table; mapping physical addresses of exact groups of associated codelets to exact address spaces, wherein each exact address space is accessible by the exact group of associated codelets for each exact address space; and mapping a given exact group of codelets to its exact address space Any access to external spaces is treated as an error.

The present invention also provides methods and systems for representing, manipulating and executing codelet sets. A codelet set is a group of codelets that can be processed as a unit with respect to dependency analysis or execution. Codelet sets provide mechanisms for developing and executing distributed applications, and mechanisms for application composability: codelet sets can contain codelet sets and they can be constructed and reused hierarchically. Even codelets can run to completion without preemption as long as their dependencies are satisfied, but they can also run on preemptive systems, either to simulate non-preemptive multi-core architectures, or because for codelets Some other properties of preemptive computing are ideal for distributed applications represented by sets. Further, preemptive OS hints can be given to minimize preemption, such as core tightness and process prioritization. In this way, the codelet's runtime can coexist with other legacy applications on the current computer system.

According to embodiments of the present invention, instead of centralized control and resource allocation, the system code (which itself is implemented by the codelet set) only initializes the platform of the codelet set to run by enabling the initial program of the codelet set. According to the present invention, an application program is broken down into independent code segments that can be executed with a minimum amount of system coordination.

System utilization and management overview :

In embodiments of the present invention, such as the examples studied in more detail below, the runspace execution model pervades all levels of system utilization and monitoring. At a fine-grained level, the execution model provides a series of codelets and their respective dependencies. The fine-grained nature of codelets allows the runtime system to allocate resources efficiently and dynamically, while monitoring performance and energy consumption and enabling scheduling changes to match the performance and power needs of the application.

The runspace system allocates available resources to a given application and provides APIs to access off-chip resources such as disks, peripherals, other node memory, and the like. Application areas (i.e. nodes where applications are available) are defined by the hypervisor. The fine-grained nature of codelets allows the runtime system to efficiently and dynamically allocate resources while monitoring performance and energy consumption and enabling scheduling changes to meet application and system performance and power goals.

In the system 101 according to the embodiment of the present invention, as shown in FIG. 1, there are five components for system utilization and management in the exemplary runspace structure 101: (1) Shared long-term file system and start application Traditional operating systems (OS), (2) a hypervisor that controls system resource allocation at the primary level, (3) a micro-OS that manages off-chip resources, (4) a runtime system that provides task synchronization and manages power consumption and performance, and (5) a hardware abstraction layer that provides microOS portability and allows access to new peripherals. According to these embodiments, a threaded virtual machine (TVM) replaces a conventional OS to provide direct access to hardware and fine-grained synchronization between codelets. The TVM should not be understood here as a separate component, in fact it is implemented by the runtime system and the micro-OS.

Figure 1 outlines the overall interaction between components.

HyperManager :

The hypervisor allocates global resources to a given application based on user parameters and optionally application-specified parameters. This includes how many nodes should be used, and in some embodiments, the degree of connectivity of the nodes. The hypervisor sets the application domain and defines the microOS running on each node. The hypervisor then loads application-specific parameters (eg, command line arguments, environment variables, etc.) and instructs the runtime system to start the application. The runtime system starts the user application by starting one or more codelets on the core starting at the main program start pointer. User applications may request that more codelets be spawned at runtime. In addition, user applications interact directly with the runtime system for task synchronization. All off-chip I/O is mediated by a micro-OS that serializes requests and responses channeled through serial conduits (eg, disk I/O, Ethernet, node-to-node communication, etc.). In addition, the micro-OS helps the runtime system communicate between nodes to other runtime system components. The hardware abstraction layer provides a common API to other platforms to discover new peripherals for micro-OS portability.

The following paragraphs outline the overall structure and functionality of the different components involved in system utilization and maintenance.

Threaded Virtual Machine (TVM):

TVM provides a framework to divide work into small non-preemptive chunks called codelets and schedule them efficiently at runtime. TVM replaces the OS with a thin layer of system software that interfaces directly with the hardware and largely shields the application programmer from architectural complexity. Unlike a conventional OS, TVM is able to expose resources that are critical to achieving performance.

Figure 2 shows an embodiment of a TVM. TVM abstracts any control flow, data dependencies, or synchronization conditions into a unified data acyclic graph (DAG), and the runtime can decompose the DAG into small code mechanisms. On top of the DAG, the TVM also overlaps another DAG that expresses program locality using the notion of scope. In an embodiment of the invention, a codelet can access any variables or state established on the parent (eg, 201 ), but siblings (eg, 202 and 203 or 204 and 205 ) cannot access each other's memory space. Using this range, the compiler and runtime can determine the appropriate working set and available concurrency for a given graph, allowing the runtime to use power-optimized models to set the tightness and load-balancing features to schedule resources to codelet execution and system Percolation of state or scope variables.

Unlike conventional OS frameworks, TVM maintains a fractal semantic structure and gives scheduling and percolation control over runtime to optimally execute tasks. By following this fractal nature, the enabled programming model will be able to provide substantial information to the runtime system. Thus, unlike monolithic threads with unpredictable and uncomplicated caching mechanisms, the granularity and static and dynamic nature of the runtime overhead are both managed as tightly as possible to provide greater power efficiency.

Runtime system:

The runtime system is implemented in software as a user library and in hardware by a runtime system core to serve several execution cores. In an embodiment, the runtime system core may be distinct from the execution core, or may have specific hardware to help the runtime operate more efficiently. In an embodiment, an execution core may execute runtime system tasks, and there may or may not be a dedicated core for runtime system task execution.

According to an embodiment of the present invention, configuring and executing a dynamic runtime system involves a method of optimally allocating data processing resources to data processing tasks. The method involves: at compile time, analyzing potential code and data allocations, placements and migrations; and at runtime, placing or migrating codelets or data to practice the opportunities presented by actual code and data allocations; and in some embodiments , copying at least some data from one site to another, in anticipation of migrating one or more codelets; and moving codelets to other underutilized processors.

Embodiments of the present invention relate to a data processing system including hardware and software to optimally locate a codelet set in the system. Elements of the system include digital hardware and software based components for: (i) exchanging information between sets of processing resources in the system related to metrics related to optimality of sets of codelets between processing resources Placement is related; (ii) determining which of the processing resources to locate the one or more codelets in the set; and (iii) mapping the one or more codelets to the one or more processing resources based on the determination. In various implementations, the mapping may involve data and/or codelet migration triggered by sub-optimal data locality. In some scenarios, small code and data are migrated depending on the cost of the migration. In an embodiment, migration cost drivers include one or more of the following: amount of data or code to be migrated, migration distance, overhead of synchronization, memory bandwidth utilization, and availability.

The runtime system may use compile-time annotations or annotations from current or previous executions of the specified codelet optimal efficiency environment. A related method in an embodiment of the present invention involves compiling and running a computer program for maximum economy of program execution. The method, at program compilation time, determines an optimal efficiency execution environment for portions of the program called codelets; and correspondingly, at program run time, locates the codelets for execution in their optimal efficiency execution environment. Furthermore, in some embodiments, the determination of the optimal environment is based on indications of program source code such as: (i) compiler directives; (ii) function calls, where a type of functions provide information about the optimal execution environment for said function; (iii) loop bodies with certain characteristics such as striding, working set, floating point usage, where the optimal execution environment has been determined by a similar data processing platform The cycle-like system operates to be predetermined. An optimally efficient execution environment for executing a given codelet may be defined by criteria such as: energy consumption, processing hardware resource usage, completion time, minimum completion time for a given energy consumption budget.

Internal hardware/software runtime stack:

In an embodiment of the present invention, for example in the system 300 shown in FIG. 3 , the runtime system core 301 is co-located with the event pool memory 302 . In an embodiment, tasks of the runtime system may operate on dedicated runtime system cores, or by an execution core. The event pool 302 contains upcoming fine-grained codelets, application and system goals (eg, performance and power goals), and data availability events. The event pool 302 can be an actual shared data structure such as a list, or a distributed structure such as a call-back system that is called when resource utilization changes (such as when a queue has free space; a processing element is available for work; or a mutex is available). . The runtime system core 301 responds to events in the event pool 302 . According to an embodiment of the present invention, there are five managers running on the runtime system core 301: (1) data percolation manager; (2) codelet scheduler; (3) codelet set migration manager; 4) load balancers and (5) runtime performance monitors/governers. In some embodiments, these managers work cooperatively by operating in close proximity and sharing runtime state. Figure 4 shows the input, output and interaction 401 of a manager running on the runtime system core 301 of an exemplary embodiment. The data percolation manager percolates data dependencies (i.e. prefetch input data when available) and code dependencies (i.e. prefetch instruction cache) when appropriate. When all input dependencies are satisfied, the codelet scheduler places codelets in a work queue, thereby re-prioritizing ready codelets in the queue in some scenarios. The execution core repeatedly accepts tasks from the work queue and runs them to completion. In the process of running codelets, the execution core can create codelets or threads and place them in the event pool. The runtime performance monitor/governor monitors the power and performance of the execution cores and may make adjustments to reduce power (e.g., scale down the frequency and/or voltage of the cores; power down the cores; or shift some or all of the work queues to Migrate work to other compute areas on the chip and turn off cores) or increase performance (e.g., scale up frequency and/or voltage; turn on cores; recruit more work from other compute areas or turn on different compute areas and combine them into applications ). The load balancer analyzes the work queue and event pool and determines whether the work should be done locally (that is, within this compute area) or migrated elsewhere. The codelet migration manager works with other runtime system cores on the node and remote nodes to discover the optimal destinations for sets of codelets and migrate them appropriately. Codelet migration can also be triggered by bad data locality: if many codelets in a codelet set request data that is located on another node, it may be better to relocate the code than the data.

These managers also communicate together in a cooperative manner to achieve goals of common interest with eg a minimum completion time for a given energy budget. For example, if a performance manager wants to power down and a load balancer wants to shift more work locally, then co-locating the two managers on the RTS core means that they can simultaneously deliver the best course of action for their targets and Make quick, deterministic actions. Thus, these subsystems provide control structures that model internal performance and derive set points based on generalized role (GACT) objectives. The goal of the system is to provide the highest performance with minimum energy consumption in an energy proportional manner constrained by GACT. In an embodiment of the invention, these functions rely on the runtime system core to communicate asynchronously with the main runtime system core by sending load and power indicators and receiving target objects. It is the job of the main runtime system core to monitor the overall performance/power distribution of a given application on the chip and adjust the performance of each compute region appropriately (which may include frequency, voltage and on/off status of individual cores).

The main runtime system core of each node assigned to the application communicates asynchronously with the main runtime system core of the so-called head node of the application and exchanges performance metrics and target objects such as completion time, energy consumption and maximum resource constraints (e.g. , memory space, nodes, network links, etc.). The hierarchical and fractal management structure of the runtime system hardware reflects the hierarchical nature of the execution model. Collectively, the main runtime system core of the node running the application performs hypervisor tasks as described below in the hypervisor section. The runtime systems communicate with each other and provide feedback (for example, a local runtime core determines that the workload is low, tells the main runtime core, and accepts more work), so that the entire system is self-aware.

In an embodiment of the self-aware operating system, a fractal layered network of monitoring areas enables management of the data processing system. For example, in a basic cluster, zones can be: cluster, node, socket, core, hardware thread. A process (which may be a scheduler) at each leaf domain monitors the health of the hardware and applications (eg, energy consumption, loading, progress of program completion, etc.). Monitors higher in the hierarchy aggregate information from their subdomains (and may optionally add information in their domains - or require all monitoring to be done by subdomains) and pass information up to their parent domains. When a hardware component fails, it is reported up the link. Any level in the hierarchy can be selected to restart codelets running on failed hardware or passed up a link. Once a level chooses to restart the codelet, it can delegate tasks down to its sub-levels for execution. Enabled codelets can also be migrated in this way. If a level finds that its queues are getting too full or consuming too much power, it can migrate enabling codelets in the same manner as described above. Finally, if a level finds it has too few tasks, it can request work from its parent level, and this request can be followed up the chain until a suitable donor can be found.

Runtime System User API:

A codelet may create additional codelets by calling run-time library calls to define the data dependencies, arguments, and program counters of the additional codelets. Synchronization can be achieved through data dependencies or control dependencies. For example, barriers are implemented by multiplying codelets that depend on variable equations with the number of characters participating in the barrier (see Figure 5). Each participating codelet atomically adds one to the barrier variable. Mutexes can be implemented in a similar fashion: a codelet with a critical section captures the mutex as a data dependency, and releases the lock when done. However, if the critical section is short, then in some scenarios (when there is no deadlock and when the lock is in space local memory), it may be fruitful for the core to just wait for the lock. Finally, atomic operations() on memory allow many types of implicit non-blocking synchronization, such as compare and swap queue entries and atomic add increment/decrement.

micro-OS

The microOS provides non-local node resources and security at node boundaries. In an embodiment of the present invention, a micro-OS has two components: (1) specific codelets that run on the execution cores; and (2) library functions that users invoke through system calls. Specific codelets are used for event-based interrupt-driven execution or asynchronous polling of in-line devices and placing data into queues. Typical devices include Ethernet, ports on switches connecting this node to other nodes, and other sources of unsolicited input (perhaps asynchronous responses from disk-I/O). Additionally, codelets may be reserved for sequential events such as forward relay operations over a reliable communication protocol such as TCP/IP. These codelets analyze senders and receivers to ensure that specific sources belonging to the application with the node are allowed to access resources on the node or application-specific resources (eg, scratch space on disk). Access to shared resources (eg, the global file system) is authenticated by means of capabilities such as user, group, role, or access level.

Library functions allow user applications to directly access hardware without intervention or additional scheduling. Some of these functions can be implemented directly in hardware (eg, LAN, node-to-node, or disk writing). Other functions use low-level support to directly send and receive data from an asynchronous input polling thread via buffering, such as requesting disk access from another node. Library calls direct the user to access data assigned to its application. A user or system library can specify whether to block waiting for a response (e.g. we know it will be back soon) or to schedule codelets to run data dependencies on the result.

Library functions are designed to be energy efficient and hide latency by being tightly coupled to the runtime system. For example, a codelet that invokes a filesystem read may make a filesystem request; create a codelet to handle responses with data dependencies on filesystem responses; and leave. This allows the execution core to work on other codelets while data is in transit (rather than being held in an I/O wait state). If there is not enough concurrency, the runtime system can turn off cores or reduce the frequency of cores to allow slower calculations in the face of long-latency read operations.

Embodiments of the present invention provide security in two modes: High Performance Computing (HPC) mode, where one application owns all nodes; and non-HPC mode, where multiple applications can co-exist on a node. In HPC mode, it is generally sufficient to enforce security on node boundaries (ie no checking of on-chip accesses other than kernel/user memory space and ROM). It is also sufficient for user applications to know the logical mapping of nodes in their application (ie, nodes 0 to N-1, where N is the number of nodes in the application). The microOS knows to physically map node IDs to logical IDs, and rewrite addresses when appropriate. Additionally, when the microOS gets input from outside the node boundary, it verifies that the data belongs to that node. Therefore, on-chip security includes keeping the kernel code separate from user code and protecting the user's ROM from writing. In non-HPC mode, the microOS allows nodes to communicate with external peripherals but generally not with other nodes. Validate input in the same way. Additional security is performed by hardware configured by the hypervisor as described in the hypervisor section. Security can be enforced at the coarse-grained application level or at the fine-grained codelet level. At the codelet level, since data dependencies and block sizes are known at run time, it can be implemented by hardware by using guard pointers (like those used on M machines) or by using invalid pages or canaries (used in ProPolice or stack protection) to provide security around data objects.

HyperManager:

The hypervisor is responsible for allocating resources to user applications. In an embodiment of the invention, it is physically resident on all nodes and partly on the master system. One or more codelet sets on each chip are available for hypervisor functions. They are resident in the runtime system core and execution core, and generally follow the same fine-grained execution model as other codelet sets in the system. The implementation of the hypervisor on the host software maintains the state of all resources allocated to all applications in the system. When starting an application, a generalized role (GACT) can specify a set of execution environment variables, such as the number of nodes and power and performance goals. The hypervisor places applications in the system and allocates resources such that nodes in the application space are contiguous and well matched to GACT application requests. Once a set of nodes is allocated, the master hypervisor communicates with the hypervisor instance on each node to allocate the nodes, passing the application code image and user environment (including power and performance targets if applicable), and signaling the runtime time system to start applying. The hypervisor informs the micro-OS and the runtime system that resources are allocated to applications. The hypervisor instance on the node then monitors application performance and works with other hypervisor instances and runtime system cores on other nodes assigned to the application to achieve success by managing the relationship between power, performance, security, and resilience rate/performance goals, thereby maintaining an energy-proportional runtime power budget (see Figure 6 for hierarchy 601 of overall system, hypervisor, and runtime system interaction). MicroOS threads and libraries provide security of application data and environments on all nodes distributed to the application.

In non-HPC mode where multiple applications can co-exist on one node, the hypervisor creates compute regions from core sets. Each application's RAM is partitioned, and user applications cannot write to each other's DRAM or on-chip SRAM. This can be implemented by a power-efficient basic memory management unit (MMU) or by a generalized virtual memory manager (VMM) on legacy machines. During the application startup phase, the hypervisor determines the address prefix and size of each partition, and the MMU can immediately rewrite the application address. In general, addresses mapped into application memory space can be accessed in this manner.

Hardware abstraction layer:

The Hardware Abstraction Layer (HAL) allows the micro-OS and user applications to query hardware device availability and interact with the hardware in a uniform manner. Devices can be execution cores, disks, network interfaces, other nodes, etc. Parts of the system are accessible by user applications through file descriptors. MicroOS library function calls such as open, read, write, and close provide the application with a basic hardware abstraction layer. The driver interacts with the HAL, where a series of memory reads and writes. The HAL implementation translates these requests into hardware platform dependent bus transactions. This allows the user to reuse the driver code on a different base platform.

Additionally, the application can query the hardware or runtime system for the number of nodes available to the application, the number of execution cores on the chip, and memory availability to help determine how to partition the problem. For example, if there are a thousand cores, the application can divide a million iterative loop into a thousand iterative codelets; if there are only four cores, then it can divide the work into coarser-grained chunks, because the The hardware gets more concurrency and less overhead with less codelets. In various embodiments, the optimal size of a block may be, for example, the rounded integer quotient of (1) the maximum number of work units that can be performed in parallel divided by the amount of processing elements available to the application; different sizes such that the maximum difference between the minimum and maximum block sizes is minimized; or (3) allow application partitioning to be done within the provided time budget while maintaining the maximum size within the provided energy budget.

Self-optimizing OS:

Operating system services are performed by the microOS and runtime system and managed by the hypervisor. Together, these components make up the exemplary self-aware operating system 701 described in the embodiment shown in FIG. 7 . The self-optimizing nature of the runtime system is achieved by: (1) the self-awareness of the execution system; (2) the self-awareness of the OS; and (3) the interaction between (1) and (2). As shown in Figure 7, the OS, hypervisor, runtime system, and execution units communicate with each other and with their adjacent levels to provide a feedback observe-determine-control loop.

This section describes an embodiment of the self-optimizing system model 701 .

(1) Self-optimizing loops embedded in the execution system: Implementations of the execution model feature two types of codelets: asynchronous task and dataflow codelets. In both types, the invocation of the corresponding codelet activity is event-driven. At least in the case of asynchronous tasks, invocation of codelets may additionally depend on computational load, energy consumption, error rates, or other conditions on the particular physical area to which the task may be allocated. Self-optimization can also be applied to performance-aware monitoring and adaptation.

(2) A self-optimizing loop embedded in the operating system: The self-optimizing OS observes itself, reflects its behavior and adapts. It is goal-oriented; ideally, it is sufficient for the system client to specify goals, and the system's job is to figure out how to achieve them. To support these self-optimizing functionalities, the OS observer agents (i.e., the runtime system kernel and hypervisor) of the implementation are equipped with performance monitoring facilities that can be programmed to observe all aspects of program execution and system resource utilization, and can Energy efficiency monitoring facility to observe system power consumption when OS is requested at different time slots or specific locations/regions.

In an embodiment, the OS determines that the agent (code running on the core of the runtime system) is equipped with appropriate model builders and learning capabilities so that it can take timely and effective actions to self-correct and adapt to achieve goals. In some embodiments, the OS self-optimizing loop enables the control theory method to achieve its goals. Figure 7 shows the interaction between (1) and (2): connecting the control loop in the OS and the control loop in each execution system. The OS control loop can query the executing systems about their operating status, resource usage, energy efficiency, and error states to make educated determinations to perform system-level global control and adjustments. At the same time, each individual execution system can seek help from the OS to solve problems in its own control that can be better solved at the OS level.

To efficiently use the runspace system and method, an application developer can provide instructions that are annotated by the system at compile time and that result in better initial static allocation, better run-time (dynamic) allocation, or both. By. Figure 8 shows an explicit language element (801) in C where the application programmer is alerted that the system is "resource stalled", which may indicate that code can be migrated to low power, slow execution units. Reference numeral 802 denotes an implicit instruction: a specific API call using low-fidelity floating-point calculations. These calculations can be done cheaply on floating point processing units with very small mantissa bits, allowing greater specialization and better matching capabilities and needs within the computational domain of the system. These are some examples of user-specific instructions that the runtime can use to make dynamic determinations. In addition, instructions can be used to profile and annotate applications so that runtime can make better dynamic determinations in subsequent runs based on hints provided by the annotations.

Figure 9 illustrates an exemplary micro memory management unit. Reference numeral 901 is a processing unit with local code execution and four local physical memory blocks. Reference numerals 902 and 903 are two memory blocks owned by the same control task - owner X - and which have access to the codelets associated with said task. 902 has logical address 00 and physical address 00, while 903 has physical address 10 and logical address L01. Reference numeral 904 shows how memory accesses other than L01 appear to X owned codelets. i.e. any local logical address other than L02 is wrong for the codelet owned by X. Reference numeral 905 shows the portion of memory resident at physical location 01, which logically shows as L00 for the codelet owned by Y. All other local physical memory cannot access the Y codelet. Reference numeral 906 shows the portion of memory resident at physical location 11, which logically shows as L00 for the codelet owned by Z. All other local physical memory cannot access the Z codelet.

Figure 10 shows a simple usage example of a system including a runspace, where a generalized agent 1001 directs tasks (typically by compiling source code); starts an application 1003 and obtains a result 1004 . Concurrently, another GACT 1005 performs monitoring and system maintenance 1006 . In a typical environment, the runspace system is available over a local area network (LAN) and/or wide area network (WAN) 1007 and is conducted by interaction with a conventional front end server 1008 which communicates with a high end computer (HEC) 1009 .

Figure 11 shows an example of code and data locality observed in a run space with small code and data distribution over time. Additional attributes of a runspace may include peripheral resource requirements or allocations, processor operation encapsulation and constraints, task urgency or deferrability, and the like. The run-space system uses a metric-space distance model to initially allocate code and data to appropriate local processing elements, and to dynamically migrate code and data when it is deemed beneficial to optimize system performance relative to current goals. The system can use policy-driven optimization techniques to dynamically allocate and use exhaustive optimization at compile time. Additionally, the system can learn from previous performance data to improve future assignments of specific codelets, subroutines, tasks, and applications.

Cross cutting interaction:

Execution Model: Runtime system and microOS management, migration and propagation of codelets. They choose to run small code versions based on their runtime goals. As described above, the runtime system core manages data dependencies between codelets, thereby migrating data and codelets together, and breeding the correct version of the codelet based on runtime constraints.

Dependency is a combination of security and resilience. According to an embodiment, the security aspect of the present invention includes providing codelets with a security indication, wherein the indication indicates the restrictions or permissions to be considered when distributing the codelets and their associated data. Memory accesses outside of data binding or specified permissions will add security exceptions to be handled by the runtime system. In HPC mode, the application fully owns the nodes. Security at the core level is provided by user/kernel space memory and instruction set implementation. Security at the application level is provided by the main system, which defines the set of nodes on which the application runs, and the hypervisor, which relays information to the micro-OS running on the allocated nodes. Security at the system level is provided by a work manager on the host system that schedules and assigns nodes to applications in a mutually exclusive manner. In non-HPC mode, the system is further subdivided into mutually exclusive chip regions and memory portions, and memory and resources are mapped to prevent applications from accessing each other's data on the same chip.

Resilience is maintained by Fractal monitoring the health of the system and re-executing failed codelets. The local runtime cores in the compute region monitor the execution core health. Node-level runtime cores monitor runtime cores. The node-level runtime core is monitored by the main system. When a component fails, the codelets running on the core are restarted (if they did not create a state change in the program) or the application is restarted from the checkpoint (if the state of the program is non-deterministic).

Efficiency goals seek to maximize performance and minimize energy consumption given a set of application and system goals. This is achieved by frequency and voltage scaling at the execution core level based on code dependencies and work availability. In addition, codelets and data are migrated to where they can communicate with each other most efficiently (e.g., by keeping interacting codelets closer together) and consume the least amount of power (e.g., by moving codelets together to allow unused cluster power where the area shuts down and eliminates idle energy consumption).

Self-optimization: Self-optimization is maintained through fractal monitoring of the network (for health and performance) and runtime system rescheduling to achieve application and system goals while maintaining reliability and efficiency.

Implementation plan description:

The following describes the operation examples and application scenarios of the embodiments of the present invention with further reference to the accompanying drawings.

Figure 12 shows a computing system using codelets. Important representation steps include: 1201 providing a codelet representation system on GCS; 1202 obtaining codelet representation from GACT; 1203 converting codelets into executable or interpretable instructions and dependency representations; 1204 using on GCS 1205 executes dynamic concrete distribution and migration of executable instances of codelets; 1206 executes codelets and 1207 enables new codelets based at least in part on dependencies.

Figure 13 shows a codelet set representation system comprising the following steps: 1301 providing a specification system to assign a codelet set; 1302 providing a mechanism to GACT to construct and modify a codelet set and obtaining an initial analysis of a codelet set; 1303 providing a mechanism to GACT to execute codelet sets on actual or simulated resources; 1304 provide mechanisms to GACT to monitor running codelet sets or view historical traces of codelet sets; 1305 provide mechanisms to GACT to dynamically manipulate codelet sets; and 1306 provide GACT mechanism to profile codelet set performance and resource utilization.

Figure 14 shows an example of a codelet set transformation comprising the following steps: 1401 extracting a codelet set descriptor from a representation; 1402 transforming executable instructions; 1403 applying resource invariant optimizations; 1404 constructing, grouping and distributing instructions to direct runtime allocation, distribution and migration; 1405 applying resource specific optimizations; and 1406 generating executable text and enabling initial codelets.

Figure 15 shows an example of meta-level codelet distribution, said example comprising the following steps: 1501 use instructions to initially allocate codelet sets to computing and data resources; 1502 monitor concrete level codelet execution and resource utilization; 1503 collect modifications Opportunities for codelet set distribution; 1504 construct instructions that improve initial (compile-time) codelet set distribution; and 1505 provide resource information and arbitration to support dynamic (run-time) migration of codelet sets.

Fig. 16 shows codelet set execution and migration and includes the following steps: 1601 uses codelet set distribution instruction to distribute codelet set literals to communication resources or to simulated computing resources; 1602 provides communication between codelet set execution literals and distribution instructions Mapping; 1603 configures the codelet set to return resources and results to the system until completion; 1604 monitors resource utilization and enabled codelet queue loading; 1605 uses codelet signals to obtain or transmit status information, or monitor codelets The system; 1606 monitors to identify and commit resources or chain requests up to higher level monitors; and 1607 removes codelet sets from enable queues as appropriate and migrates them along with the data.

FIG. 17 shows the double-ended queue concurrent access mechanism: 1702 writing and 1703 queuing. The other status of the queue is empty at 1701 and housekeeping at 1704 .

Fig. 18 shows the dequeue concurrent access mechanism, this time execute 1801 consistency check, 1802 empty queue, 1803 non-empty queue and 1804 read and dequeue. Note that one advantage of this system is that the process using the system has the integrity to handle cleanup tasks, so the queue is very robust.

Figure 19 shows concurrent access to an array (A) by atomic addition: write. The states include 1901 an initial state and 1902 an atomic update of the write pointer.

Figure 20 shows concurrent access to array (B) by atomic addition: write. The states include 2001 Data Write and 2002 Tag Update and Reader Visible Data.

Figure 21 shows concurrent access to array (C) by atomic addition: read. The states include 2101 data ready to be read and read pointer updated and 2102 read started and 2103 read done and flag updated.

Figure 22 shows a linked list, specifically an atomic addition array (A).

Figure 23 shows a linked list, specifically an atomic addition array (B).

Figure 24 shows a linked list, specifically an atomic addition array (C).

Figure 25 shows a linked list, specifically an atomic addition array (D).

Figure 26 shows a linked list, specifically an atomic addition array (E).

Figure 27 shows concurrent access through a shared array with steering.

Figure 28 shows combined network distribution increments.

Figure 29 shows single-task and multi-task execution concurrent access by atomic addition array (A).

Figure 30 shows single-task and multi-task execution concurrent access by atomic addition array (B).

Figure 31 shows single-task and multi-task execution concurrent access by atomic addition array (C).

Figure 32 shows single-task and multi-task execution concurrent access by atomic addition array (D).

Figure 33 shows single-task and multi-task execution concurrent access by atomic addition array (E).

Figure 34 shows a codelet computing system scenario showing the roles of different users with respect to the system.

Figure 35 shows a general exemplary structure at the microchip level. Note that the memory class is non-specific, and it is intended to transfer local memory (with fast access) to a hierarchy of non-local memory. For example, LI may be implemented as a register file, SRAM, etc.

Figure 36 shows the board-level/system-level general structure; likewise, shows the range of performance and globality.

Figure 37 shows the assignment of codelets and codelet sets. There are many equivalent ways to specify codelet sets. Specifications are usually signaled by native language constructs, or even by non-executive annotations or choices made through integrated development environments, through the use of specific metalanguages. Codelet sets are authorable and can be defined to inspire other codelets or sets of codelets. GACT builds functionality by building codelet sets from basic codelets, and then by combining the sets into larger sets that include all applications. The function setDependency allows expressing a dependency between two elements of one codelet set or two elements of different codelet sets. In one embodiment, the function implementSet is called at runtime to construct dependency graphs and convert them into pointers. Additionally, in an embodiment, the compiler is modified to generate dependency information from code, even if the dependency information is not provided by GACT.

Figure 38 shows the double buffer calculation (A). Note that each codelet set has initialization and cleanup routines to start the system and clean up and fire up export dependencies. In some embodiments, initialization and cleanup tasks may be statically optimized at compile time or dynamically optimized at run time. Runtime systems are isomorphic when represented as Petri nets, which are graphs of positions and transitions. Locations extend the data flow model and allow the representation of data dependencies, control flow dependencies, and resource dependencies. In one embodiment, the system executes the high priority tasks first and then proceeds to the high priority tasks. This allows scheduling of certain system-critical codelets, such as tasks that maintain concurrent resource access to the system. If all execution cores work on Compl and then on Comp2, then suddenly most cores will have no work until copyl and copy2 are done. Therefore, codelets that generate more codelets are given higher priority so that the run queue is never empty. In the following description, once the system is started, it executes at least some computation codelets sequentially, since they have high priority when replica codelets are available.

Additionally, in the double-buffered computation example, the exemplary index 1024 bound indicates that when Init ends, it enables 1024 the Compl codelet. Similarly, an exemplary index bound of 8 replicated codelets is fired in the replicated codelet set. Note that the number 8 is used because a system may have many processors requiring DRAM bandwidth to arbitrate among them. Thus, while the overhead (context switching) is small, a codelet system can use fewer execution cores to achieve the same sustained bandwidth, resulting in improved application processing throughput. In another embodiment, the system may dynamically provide the location into and back from the copyl, where there are always 8 tokens in the location. Similarly, the same optimization can be performed on copy2. Finally, in another embodiment, the two locations can be fused into the same location, and the replication function can use the same pool of DRAM bandwidth tokens. In this case, if the computation takes longer than the copy, then the system guarantees that copy1 and copy2 do not happen at the same time. This is an example of the expressive power of the resource constraints of petri nets, such as memory bandwidth, execution units, power, networking, locks, etc.; and illustrates that codelet sets can exploit said expressive power to enable high-parallel, high-scalability applications build. Note that at 2702, deltaT implies that SignalSet(buffer_set[0]) is executed before SignalSet(buffer_set[1]).

Figure 39 shows the double buffer calculation (B). At 3901, Init Set 1 is signaled, while at 3902, Init Set 2 is signaled and an exemplary number of 1024 codelets is computed.

Figure 40 shows the double buffer calculation (C). At 4001, task Comp2 is in the queue, but the execution core will continue to work on Comp1 when the system is operating in first come first serve mode unless there is a priority difference. At 4002, Compl completes, and the high priority task "Clear" is placed. Comp2 now continues. In other embodiments, work may be done in ways other than first-in-first-out, such as last-in-first-out to give stack-like semantics. This implementation is suitable for shared recursive application work.

Figure 41 shows the double buffer calculation (D). At 4101, Comp2 can continue, but at least one execution unit is used for the high priority task copy(8). At 4102, Comp2 continues, but has allocated more execution units to the copy function. The system cleans up resources after copying.

Figure 42 shows the double buffer calculation (E). At 4201, the system will check to see if the completion marker is in buffer 1 . At 4202, the Compl codelet is initialized.

Figure 43 shows the double buffer calculation (F). In 4301, the Compl codelets follow the existing Comp2 codelets. In 4302, Comp2 completes and Comp1 continues.

Figure 44 shows the double buffer calculation (G). Finally, at 4401, the high-priority codelets of replica set 2 are initialized, and Compl continues. Note that codelets can receive signals at any time, even during their execution. This enables code and data migration to better utilize computing resources. To summarize, some notable aspects may include: (a) prioritization; (b) balancing concurrency with queue space; and (c) extensions out of data streams, which may include, for example, early signals, event streams, and/or make programmers can affect scheduling.

Figure 45 shows matrix multiplication with SRAM and DRAM. At 4501, the system copies blocks of matrices A and B from DRAM to SRAM and computes matrix C in SRAM. At 4502, each block of C is copied back to its proper location in DRAM.

Figure 46 shows matrix multiplication double buffering/DRAM. In this case, codelets are used to double-buffer DRAM accesses, thereby reducing the latency of the accesses; this is illustrated in the section of code 4602 in parentheses.

Fig. 47 shows an example of calculating LINPACK DTRSM (Double Triangle Positive Solution Multiple). 4701 shows initial dependencies. Once the matrix multiplication is done for the first row and column, the system can move on to the next data set.

Figure 48 shows run-time initialization of a codelet set for the DTRSM case. Note that Init() is called with a parameter indicating how many codelets to generate. 4802 shows some optimizations that can be performed on a codelet implementation of DTRSM.

Fig. 49 shows an example of quick sort. At 4901, the control flow path is data dependent. If the dependency was previously resolved/satisfied, the dependency may be conditionally set based on codelet output or intermediate state. 4902 shows a Petri net representation of the quicksort graph. With this representation, the thread will work on the first half until the swaplet has no incoming data (either because there is no data or because all dirty data is on the side). When the execution unit does not have a high-priority codelet, it uses a low-priority codelet, eg, to wait at a barrier. At this point, the "move" codelet clears and moves the pivot to the correct position.

Figure 50 shows an extensible system function with an application codelet set. Because system functionality is fluidly integrated with codelet-set applications, system designers have great flexibility in balancing system overhead with system services. For some uses and applications, there may be little to no system software, but in other cases, extensive monitoring and debugging may generate more system tasks than application tasks running at a given time.

Figure 51 illustrates the conversion of existing program code to multitasking, showing how multitasking input-output tables can be used to develop concurrency evaluation of code through small code sets. Construct priorities such that sequential tasks necessary to enable one or more subsequent concurrent tasks have high priority. The mapping of specific elements of the input variable set to the output variable set allows the receiving function to begin processing as soon as the first instance is available. Counting the number of separable instances allows system software to distribute codelet execution, thereby allowing high CPU utilization and exploiting data locality.

Figure 52 shows "black box" code running with multitasking code, which shows a scenario 5201 where the library code has been converted to a small code set, but the black box user code 5202 is still in inherent order. In other embodiments, the prioritization may be conservative, assuming all black box values are required for subsequent processing; or statistical, based on performance evaluations from previous runs or previous cycles of the same run; or both. Can.

Figure 53 shows the improved black box code running with the multitasking code. In this case, parts of the black-box code can be marked by the user, so it can be used for concurrent execution. The multitask 5302 before the original black box task corresponds to the function F25303. The initial portion of black box task 5304 corresponds to reconstruction function BB1a, and the result of 5302 is used when available to convert the initial portion to run currently. The next part of the black box function is still inherently sequential and still black box to be done before subsequent operations. Note that in an embodiment, speculative execution of subsequent functions may be performed, providing a way to gain concurrency during the execution of 5306. Reference numeral 5308 is a third part of the refactored black box function, which corresponds to function BB1c and allows concurrent execution of library calls 5310 corresponding to MP25311.

In addition:

Various embodiments of the invention may address performance optimization of an application relative to some performance measure or relative to some resource constraint. Exemplary performance measures or constraints may relate to, but are not limited to, the total run time of the program, the run time of the program in particular portions, the maximum delay before executing a particular instruction, the amount of processing units used; the amount of memory used; the use of register files; Use of cache memory; use of level 1 cache; use of level 2 cache; use of level 3 cache; use of level N cache, where N is a positive number; use of static random access memory; dynamic random access memory Access memory usage; Global memory usage; Virtual memory usage; Amount available for use rather than for program execution Processor; Amount of memory available for use rather than for program execution; Energy consumption; Peak energy consumption ; the lifetime cost of the computing system; the amount of register updates required; the amount of memory clears required; the effectiveness of security enforcement and the cost of security enforcement.

in conclusion:

This detailed description provides a description of exemplary system operating scenarios and application examples for embodiments of the invention discussed previously. To describe possible implementation examples of the inventive concepts and related invention utilization scenarios, specific application, structural and logical implementation examples are provided in this and related patent applications. There are, of course, numerous alternative ways of implementing or utilizing the principles of the invention as set forth above, in whole or in part. For example, elements or process steps explicitly described or illustrated herein may in various embodiments be combined with each other or with additional elements or steps. The elements may also be subdivided without departing from the spirit and scope of the invention. Additionally, in various embodiments, aspects of the invention can be implemented using application and system software, general and special purpose microprocessors, custom hardware logic, and various combinations of the above. In general, those skilled in the art will be able to develop different versions of the described embodiments and various modifications, which are included in the spirit of the invention according to the principles of the invention, even if they are not individually described herein. and range. Accordingly, the specification and drawings are intended to be illustrative only and not restrictive, with the true scope of the invention being indicated by the following claims.

Claims (10)

1. one kind is used for distributing data processing system resources to the task of one or more application programs Method, described method includes:

A) obtaining one group of little code being configured to implement at least one task, wherein each little code is to join It is set to when can use to the required input of each little code by the instruction block that gone to of non-preemptive ground；

B) dependency of little intersymbol described in described group is determined；

C) the described dependency of described little intersymbol it is at least partially based on and based on data processing system resources Availability, dynamically map given little code in described group to data processing system resources collection to perform Described given little code.

2. the method for claim 1, wherein said mapping includes selected from consisting of The function of group: place, position, reorientate, move and migrate.

3. the method for claim 1, wherein said mapping includes selected from consisting of The function of group: determine the time started performing described given little code, and determine that execution is described given little The position of code.

4. the method for claim 1, wherein said mapping includes being selected from based at least one The standard of the group consisted of performs mapping: the 1) performance metric of improvement application program, and 2) Improve the utilization of described data processing system resources, and 3) maximize application program performance metric, Observe given resource consumption object set simultaneously.

5. the method for claim 1, wherein perform described mapping with relative to choosing freely with The measurement of the group of lower composition carrys out the performance of optimization application:

The total run time of described program；The operation time of program described in specific part；Perform specific Maximum delay before instruction；The amount of processing unit used；Memory-aided amount；Register file Use；The use of cache memory；The use of on-chip cache；Making of second level cache With；The use of three grades of caches；The use of level-N cache, wherein N is positive number；Static The use of random access memory；The use of dynamic random access memory；The use of global storage； The use of virtual memory；May be used in not for the amount processor performing described program；Available In using the amount not for the memorizer performing described program；Energy expenditure；Peak energy consumes； Calculate system lifetim cost；The amount that required depositor updates；The amount of required core dump memory clear；Safety Compulsory usefulness and the cost of security enforcement.

6. the method for claim 1, wherein performs described mapping with choosing freely following group Operation in the resource constraint of the group become:

The total run time of described program；The operation time of program described in specific part；Perform specific Maximum delay before instruction；The amount of processing unit used；Memory-aided amount；Register file Use；The use of cache memory；The use of on-chip cache；Making of second level cache With；The use of three grades of caches；The use of level-N cache, wherein N is positive number；Static The use of random access memory；The use of dynamic random access memory；The use of global storage； The use of virtual memory；May be used in not for the amount processor performing described program；Available Amount in the memorizer used not for the program of execution；Energy expenditure；Peak energy consumes；Calculate System lifetim cost；The amount that required depositor updates；The amount of required core dump memory clear；Security enforcement Usefulness and the cost of security enforcement.

7. the method for claim 1, wherein performs described mapping to seek the time-varying of target Mixing, wherein said mixing changes over due to the factor selected from the group consisted of: pre- The fixed change changed and dynamically occur.

8. the method for claim 1, also includes instruction set during application compiling, to help reality Row described acquisition, described determine or described dynamically map in one or more.

9. method as claimed in claim 8, during wherein said compiling, instruction is selected from consisting of Group: required floating point unit, required floating point precision, the frequency of access, the locality of access, stop Stagnant access, read-only data type, initial read-only data type, final read-only data type and have ready conditions Read-only data type.

10. the data handling system being made up of multiple cores, including:

A) multisystem administration agent collection, described collection includes following one or more: data diafiltration manages Device, little code scheduler, little code migration manager, load equalizer, power regulating eqiupment or performance manager, Wherein each little code is arranged to when can use to the required input of each little code be held by non-preemptive Row is to the instruction block completed；With

B) the plurality of core intermediate range is optimized alternately with cooperation mode for described system management agent collection The component that sequence performs.