Method, computer program, and computer readable medium for scheduling in a multicore architecture

Method, computer program, and computer readable medium for scheduling of multi-core architecture

METHOD, COMPUTER PROGRAM, AND COMPUTER READABLE MEDIUM FOR SCHEDULING IN A MULTICORE ARCHITECTURE

The present invention is related to a method and device for scheduling threads in a multi-core structure.

In recent years, there has been a tendency to manufacture processors with multiple cores to maximize silicon efficiency (ie, "application-available" MIPs/mm2 or MIPs/mW). Since a thread definition includes an execution state, a command stream, and an autonomous package of a data group, the multi-core structure is ideally suited for executing applications based on threads, and the thread definition can be executed concurrently with other threads.

Scheduling is the general name for the discovery and allocation of the most suitable thread (ie, instruction set) to execute on a specific processing resource, which is required by both the application and the underlying hardware platform when it is executed.

Simultaneous execution in a multi-core architecture accompanied by the availability of multiple cores suitable for executing a particular thread will cause additional problems in the scheduling for allocating threads in these multi-core architectures.

According to a first aspect of the present invention, the One of the proposed multi-core processors provides a method of scheduling executable transactions, which is more commonly referred to as threads.

By providing a multi-level scheduling system, more commonly referred to as a hierarchical scheduling system, the present invention allows the construction of one or more complex scheduling algorithms in addition to the simpler scheduling algorithms. The ability to use this complex scheduling algorithm improves the performance of an application that contains multiple threads during execution. The present invention improves the execution performance of an application program by more effectively allocating the executable transactions or threads to processing resources. This can increase execution speed and reduce bottlenecks on specific resources. It can also increase the use of the less active parts of the multi-core processor.

In this preferred embodiment, the present invention is implemented by a dedicated hard-coded and therefore effective embodiment. The preferred hard-coded embodiment is located in a server-client topology, which includes a system server (herein referred to as SystemWeaver) and a client for each processing resource or core in the multi-core processor. In other embodiments where the ability of processing resources is questionable, a single client may aggregate access to multiple processing resources.

In order to further enhance the performance of the integrated system of the present invention, the preferred embodiment uses pointers in a dedicated memory for scheduling allocation, storing values for selection purposes, and so on. These indicators preferably contain fields to store parameters when creating the schedule selection, or only store other important values. Hereinafter, this field is collectively referred to as metrics or operators.

According to a second aspect of the present invention, there is provided a method for scheduling executable transactions in a multi-core processor, the executable transaction defines an application program, and the multi-core processor has a plurality of processing elements, and the method Contains dimension Protects a hierarchy of executable transaction schedulers, where the hierarchy is used to schedule executable transactions based on the application's requirements when in use, wherein each hierarchy of the scheduler includes at least one row Wherein the at least one scheduler includes at least one rule to rank the executable transactions on one or more of the processor elements as a sequence of transactions that are most suitable for execution.

According to a third aspect of the present invention, a method for managing power consumption in a multi-core processor is provided, as described in item 37 of the scope of patent application.

In a situation where a multi-core processor has multiple processing resources, each of which can execute a specific thread, the present invention allows these multi-processing resources to be collectively placed in a pool. Then the pool of this processing resource is allocated threads. However, in this case, when the number of threads that need to be executed does not exceed the execution capacity of the pool, that is, when some processing resources in the pool are not utilized or not fully utilized, the present invention allows Each processing resource is placed in a power saving mode. The processing resource can even have multiple different power saving levels.

Preferably, when the thread execution load needs it, the processing resources are moved out of the power-saving mode, or at least moved back to a lower power-saving mode with lower costs associated with the full power mode.

According to a fourth aspect of the present invention, there is provided a method for scheduling executable transactions or threads in a multi-core processor, the multi-core processor including resettable logic, as described in item 38 of the scope of patent application.

In the case where one or more of the processor elements have a configuration logic, for example, in the case of a field programmable gate array (FPGA) that can configure the execution part, the present invention can utilize this logic by gathering The thread of the same configuration improves performance. This is used to reduce the need for content switching or reduce the impact Click, that is, when the configurable logic part is being reconfigured.

The present invention can also improve the performance in the case of resettable logic in the form of a regional cache that stores commands that can be executed next on the processing element in question.

This is due to the loss of the region cache, or the region cache flush can be minimized by gathering threads of execution that use the same region of the cache memory.

According to a fifth aspect of the present invention, a computer program executed by digital logic is provided, which executes the method described in item 1 of the scope of the patent application. A computer-readable medium containing the computer program is also provided.

When using the instructions described in this article, processing elements, processing resources, cores, and processors will be considered equivalents. The busy state of a processor element is equivalent to its current workload. Further advantageous features will be defined in the scope of the attached independent patent application.

According to a further aspect of the present invention, a multi-core processor is provided, the multi-core processor includes a plurality of processor elements, at least one distribution queue, and the distribution queue lists executable transactions as execution Eligibility (eligibility) sequence; and provide a multi-layer scheduler, which includes: multiple independent executable transaction scheduler, wherein each independent executable transaction scheduler includes a scheduling algorithm to Among the candidate executable transactions for execution, the most suitable transaction is determined; wherein the schedulers are linked together, and the multi-layer scheduler is used to output the most suitable executable transaction from them to at least one allocation queue.

An executable transaction can include a thread description item, which can be Choose from the state. The thread description item can be changed between multiple states according to a state transition configuration, thus identifying the executable transaction, so it can be managed among multiple executable transactions to provide low scheduling delay and the scheduling hierarchy Completeness. The scheduler may include a schedule state selected from a plurality of schedule states. The state of the scheduler is controlled to support a dynamic scheduling hierarchy, in which the scheduling hierarchy can be adjusted during the normal operation of the system, while maintaining the order and integrity of the components scheduled in the hierarchy.

The multi-core processor may further include a hardware time resource, which may be allocated to provide a watchdog timeout, and the watchdog timeout indicates that a processing resource entity has entered an inoperable state . The hardware time resource may alternatively provide a time slice timeout, where the time slice timeout indicates that a processing resource entity or a processing resource entity group is equally divided by a plurality of equally suitable transactions. A tie can include providing a tie of the time, or a tie of the proportion of time required for the executable transaction. The hardware time resource can be allocated to switch between a first mode for providing the monitor timeout and a second mode for providing the time segment timeout. The hardware time resource is preferably used to switch to the first mode when a time segment is provided over time.

The pending manager of the multi-core processor may further include a timer queue, and each timer queue is used to receive timer queue components. The timer queue element may include executable transactions. A first executable transaction in the timer queue can be related to a first time parameter. The first time parameter indicates the time-out time, and the time-out time is the time when the relevant executable transaction should become suitable for execution. Preferably, the timeout of the first executable transaction The time is closest to the current time. A second executable transaction may be related to a second time parameter. The second time parameter indicates the difference between the timeout time of the second executable transaction and the timeout time of the first executable transaction. A third executable transaction may be related to a third time parameter. The third time parameter indicates the difference between the time-out time of the third executable transaction and the time-out time of the second executable transaction.

A first executable transaction in a queue may be related to a time parameter. This time parameter indicates the difference between the timeout of the related executable transaction and the timeout of a second executable transaction that is also in the queue. Preferably, the second executable transaction is an executable transaction in the queue that has a timeout occurrence and is closest to the timeout of the first executable transaction.

The multi-core processor may further include multiple dispatch queues. Preferably, a dispatch queue is used to identify a further dispatch queue. Each dispatch queue can contain a dispatch queue description item. This gives a flexible amount of server processing resource entities, and also enables the dispatch queue description items to be continuously queried. A dispatch queue can be further used to identify an executable transaction that currently uses a processor element from a set of pre-emption executable transactions. The dispatch queue can be further used to identify a further executable transaction from the set of preemptive executable transactions, which will use the processor element in succession. This dispatch queue thus maintains the index of the latest schedule selection created by the schedule manager.

The link of the individual executable transaction schedulers used to provide the multi-level scheduler defines a scheduling hierarchy, where each executable transaction scheduler has an associated scheduling hierarchy. An executable transaction scheduler can be used to identify an executable transaction Easy scheduler, which previously scheduled an executable transaction. Optionally, the executable transaction scheduler can identify whether executable transactions originate from an allocation queue associated with a processor element. The executable transaction scheduler can identify whether the executable transaction comes from a set of preemptive executable transactions. The processing when the scheduled event is a "push" event can be optimized. When an executable transaction is scheduled by an executable transaction scheduler, the executable transaction scheduler can be further used to communicate a calibration parameter to each executable transaction schedule previously scheduled for the executable transaction Device. The correction parameter allows the transmission of the schedule selection and the maintenance of the integrity of the counter in the multi-level scheduler.

A method of operating a multi-core processor system may also be provided, which includes: providing a client; and selecting an interactive state for the client. The interactive state may include: an idle state, in which the client can be used to operate in a power management mode; and a user state, in which the client is used to execute a power management mode in a user or normal mode. Execute the transaction. Preferably, the interactive state may further include an API interactive state, wherein the client is used to execute an executable transaction in a priority state. Optionally, the interactive state may include a client shim state, where the client is used to prepare a content for an executable transaction. Preferably, the method also includes providing a server, wherein the interactive state is shared between the client and the server. Preferably, an out of band signal can be provided to change the interactive state. The server can provide the out-of-band signal. Arbitrarily, an executable transaction can change the interactive state.

Figure 1 shows a task state diagram, which is similar to One of the implementations in SystemWeaver, which is used to manage tasks or threads in a multi-core system.

Figure 2 shows the schedule point and the representation of the queue points formed by it.

Figure 3 shows the main components of a software client to fill the gaps.

Figure 4 shows a state diagram of the SystemWeaver client in action.

Figure 5 shows a conceptual scheduling framework.

Figure 6 shows a diagram of the scheduler hierarchy.

Figure 7 shows an example scheduling cone implementation.

Figure 8 shows a typical processing resource pool configuration.

Figure 9 shows the amount of displacement presented in a task description item.

Figure 10 shows a configuration for a single processor with a single processing resource entity and its mandatory scheduling root node.

Figure 11 shows a more representative scheduling framework for a single processing resource entity.

Figure 12 shows a detailed view of one of the FIFO scheduling tiers.

Figure 13 shows a representation of this type of architecture for a pool containing two processing resource entities.

Figure 14 shows an example architecture where one processing resource participates in two pools.

Figure 15 shows a configuration with five processing resource examples and two allocation pools.

Figure 16 shows scheduling analysis, strategies and operators.

Figure 17 shows the rescheduling range of an event on a basic scheduling hierarchy.

Figure 18 shows the rescheduling scope for a single two-entity processing resource pool.

Figure 19 shows the rescheduling range for a single push operation.

Figure 20 shows the sequence diagram of the rescheduling as the result of the push event shown in Figure 18.

Figure 21 shows the transfer of metrics in the processing resource pool.

Figure 22 shows the two parts of the operating state; the regular and the opposing one.

Figure 23 shows a typical time segment configuration.

Figure 24 shows a task priority difference map.

Figure 25 illustrates a situation with a single processor and three time segment tasks.

Figure 26 illustrates the same scenario as Figure 25, but with two processors.

Figure 27 illustrates a situation with three processors, three time segment tasks, and one preemptive task.

Figure 28 shows the allocation layer schedule.

Figure 29 shows the "execution priority" of a processing resource entity (PRI) when time elapses in an idle state using upward priority.

Figure 30 shows a reconfiguration management structure.

Figure 31 shows an example SystemWeaver system structure.

Figure 32 shows scheduler grouping for minimum content thrashing.

Figure 33 shows an example lag schedule configuration.

Figure 34 shows the simulation results of delayed scheduling based on the example in Figure 33.

Figure 35 shows an example hybrid scheduling algorithm.

Figure 36 shows the key to these schedules.

Figure 37 shows a system according to the invention.

Figure 38 shows the group of interfaces found around the core.

Figure 39 shows the main logical components of the SystemWeaver server entity.

Figure 40 shows the main sub-blocks of the SystemWeaver structure.

Figure 41 shows a conceptual diagram of the internal threads of the SystemWeaver.

Figure 42 shows a state diagram of the SystemWeaver scheduler layer.

Figure 43 shows the main input and output of the thread scheduler interface manager.

Figure 44 shows the flow chart of the monitoring interrupt control in each cycle.

Figure 45 shows the behavior of the time slice support logic inside the thread scheduler interface manager in each system clock cycle.

Figure 46 shows a flow chart of a dynamic timer cycle.

Figure 47 shows the main input and output of the thread scheduler input manager.

Figure 48 shows the internal structure of the thread scheduler input manager.

Figure 49 shows the main input and Output.

Figure 50 shows the thread scheduler shelf manager shelf sequence architecture.

Figure 51 shows the basic structure of the pause queue.

Figure 52 shows a flow chart of a dynamic clock cycle.

Figure 53 shows the basic representation of the operation mode of the pause logic.

Figure 54 shows a basic timer queue architecture after thread 1 is extracted.

Figure 55 shows a basic timer queue architecture after the extraction of thread 2.

Figure 56 shows a basic timer queue architecture after the extraction of thread 3.

Figure 57 shows the main inputs and outputs of the Thread Scheduler Output Manager.

Figure 58 shows the internal structure of the Thread Scheduler Output Manager.

Figure 59 shows the main input and output of the thread scheduler schedule manager.

Figure 60 shows the basic flow of repeated scheduling operations.

Figure 61 shows a single-pass scheduling operation.

Figure 62 shows the inner scheduling used for extraction and general scheduling operations.

Figure 63 shows the basic flow of scheduling between layers.

Figure 64 shows the dispatch queue processing in this inter-layer scheduling example.

Figure 65 shows repeated pool allocation in the set interval schedule.

Figure 66 shows the flow of scheduling operations through the set interval layer in Figure 65 Procedure.

Figure 67 shows the flow of scheduling at the set interval level.

Figure 68 shows a sequence diagram of a basic scheduling hierarchy.

Figure 69 shows a sequence diagram of a serial scheduling hierarchy system.

Figure 70 shows a sequence diagram of a pooled scheduling hierarchy.

Figure 71 shows the main input and output of the thread scheduler schedule manager.

Figure 72 is the interaction between the thread scheduler output manager and the thread scheduler schedule manager in a push event.

Figure 73 shows the interaction between the thread scheduler interface manager, thread scheduler output manager, and thread scheduler schedule manager in a fetch event.

Figure 74 shows the working queue structure among the sub-blocks of the SystemWeaver server.

Figure 1 shows a logic diagram of a system architecture 10 that includes functional features according to an embodiment of the invention. The architecture 10 at least includes a plurality of processing resources 150. Each processing resource may be similar to or different from other processing resources 150, and each processing resource may have a different complexity. Each processing resource can access a common system memory 140 together, and the shared data is stored through an interconnect 160. Those skilled in the art know that not all system memory 140 must be shared by all processing resources 150.

Figure 1 illustrates a task state diagram similar to that implemented in SystemWeavor, which is used for task and thread management in a multi-core system.

In a multi-core system, the scheduler provides work packages to the best resource at the best time according to a set of predetermined rules (the "scheduling"). Both the application and the underlying hardware platform need to be scheduled:-Application scheduling includes synchronization and applicability. Synchronization ensures that the resources in the system can be shared without compromising the data or even the integrity of the system as a whole. The applicability ensures that the prepared task is sent to the processing resource in a way that meets the needs of the application as indicated by the scheduling strategy.

-Platform/distribution scheduling defines a strategy for distributing application tasks among entities suitable for processing resources. This can mean sharing a processing resource among multiple users and/or multiple different algorithms.

Figure 2 illustrates a representation of a scheduled point, which is related to the queue point it generates.

The first queue point encountered from left to right is the waiting queue. The blocked tasks are stored in the waiting queue according to their priority and released by the synchronization event. The further description of the structure and behavior of the waiting queue is beyond the scope of the present invention. The second queue point is the preparation queue, which includes both the application and the allocation schedule. In Figure 2 this is divided into three logical parts: the application and the distribution queue. Conceptually, at the point between these two scheduling levels, all currently prepared application tasks have been sorted according to their applicability (described in user-defined metrics and scheduling strategies). This point is called the distribution node.

Configure a set of application-specific scheduling strategies between the distribution nodes, which determine how tasks of different levels and task entities of a common level compete Phase access to the processing resource entity. The hierarchy of this scheduling strategy is called the scheduling cone and is application specific.

A set of platform-specific scheduling strategies are configured after the scheduling cone, which determines how the most suitable application tasks are allocated to processing resource entities existing in the potential hardware platform. The hierarchy of this scheduling strategy is called the distribution cone and is platform-specific.

A scheduling strategy and the effectiveness of its implementation can be judged on a combination of one of many attributes:-Processing capacity-the number of scheduling options that can be established per second.

-Delay-the elapsed time between an event in the system and the completion of the scheduled operation related to the event.

-Predictability/decisiveness-the ability to determine how the system will behave in all states.

-Effectiveness-the efficiency with which any particular scheduling algorithm can be implemented. This can be measured for each selected command (a measure of command group efficiency) and/or silicon footprint (memory and other die area).

-Strategy-Support the diversity of strategies and the ability to combine them to form a complex hierarchy.

element

SystemWeaver has two main components: the server core and the client shimes. These can be connected in several ways. A SystemWeaver enables the system to include a server core and at least one client to fill gaps.

SystemWeaver core

The SystemWeaver core includes a hardware engine and a close memory. The memory contains scheduling configuration and dynamic description items to indicate the work unit in the system. Gather each SystemWeaver core on multiple clients, which can be a command-setting structure or a hardware accelerator. SystemWeaver communicates with each client separately through two logically separated data paths:-An out-of-band signal to warn the client of a change in the system state that requires attention. The SystemWeaver core is the protagonist of this interface, which is typically implemented as a break (assumed here and below).

-The client can ask for a data path of SystemWeaver. The client is the protagonist of this interface, which is typically implemented as a bus, duplex serial interface, or any other two-way implementation.

The SystemWeaver core must be started during the startup process. Typically a client will be designated as the startup protagonist and will start SystemWeaver, and its associated memory will represent the rest of the system.

SystemWeaver client fills the gap

In a typical configuration, each client has an independent client gap filler, but a more conservative implementation can aggregate many client gap fillers. Can use hardware or software to implement client-side fill-in. Figure 3 illustrates the main components of a software client to fill in the gaps:-The SystemWeaver HAL implements the command formatting required by the SystemWeaver core registration interface.

-The SystemWeaver API enables the application to establish a call to the SystemWeaver on a task-based abstraction.

-The user thread uses the SystemWeaver task management Capability of the application thread. Any entity in the process has only one user thread directly managed by each independent client.

-The client side fills in the out-of-band signal service (typically interrupt service). The client management content is mainly located in the processing resource entity, which ensures integrity preservation through task switching and preemption. Typically, the client gap filler contains an unknown part of the structure and a specific part of the command group structure.

-The idle agent implements a management task that handles the power reduction mode of independent processing resource entities or giant structures.

Figure 4 illustrates a state diagram in the SystemWeaver action. The client side fills in to perform two main functions:-The "content" in which the processing resource entity executes (for a traditional processor, the content can include processor stacking space and content, registration value, program counter, etc.) Management (allocation, storage and recovery at appropriate time). There are two types of content-user or task content, which is the content in which a user task is executed, and processing entity specific content, which is a content dedicated to the client's gap-filling management operation.

-Operation mode (available in a traditional processor user (normal) and manager (prioritized) mode, which defines the right to access certain critical system resources-for example, unlike a manager mode task, A user-mode task will not be allowed to access resources, which may improperly influence other user-mode tasks to share the processing resources).

The following description is for general purpose processors, even if all client types are similar.

-"Idle" state-in the idle state, the user defines the performance The algorithm can utilize the power reduction provided by the end processing resource entity (such as clock gating or other low power states) or the system structure as a whole (such as clock gating or reducing or eliminating the power supply to a specific processing resource entity) model. However, in this state, the processing resource entity can operate in a priority mode and the processing resource specific content will be used.

Note that the SystemWeaver server does not instruct the client to enter the idle state-the client enters the idle state because it does not have a scheduled task. Each client remains in the "idle" state until it is instructed to respond via an out-of-band signal (typically an interrupt) from the SystemWeaver server.

-"Client-side gap-filling" status-The client-side gap-filling status manages the user's execution content and idle tasks. When in the "client-side gap-filling" state, the client-side gap-filling stores the content of any tasks that have been executed and preempted, or have been blocked and replied or created for the next execution of the task ( In the case of the idle task, this is the specific content of the processing resource entity). However, in this state, the processing resource entity can operate in a priority state. At any time, the client side fill can be operated in the specific content of the processing resource or the content of the user or task.

Due to the out-of-band signal from the SystemWeaver server (transition from the "user" or "idle" state to the "user fill-in" state) or because the running task has become a blocked SystemWeaver API call ( The "SyWAPI" state changes to the "client gap filling" state, for example, due to the failure of trying to lock a signal) to enter the "client gap filling" state. When the processing is completed, the client gap filler can switch to the "client gap filler" state It is the "idle" state (if the processing resource entity has no outstanding tasks) or the "user" state (if the processing resource entity has suitable tasks) without any further external communication.

-"User" state-when in the "User" state, the client side fills in and executes the user application code. However, in this state, the processing resource entity can normally operate in a "user" or "normal" mode. The "user" state can be fully manipulated in the user or task content.

Can enter the "user" state from the "client-side gap filling" state due to starting or resuming a user task, or enter the "use" state from the SyWAPI state due to a return from a SystemWeaver server API callBy" status.

The client gap filling can be converted from the "user" state to the "client gap filling" state due to task completion or preemption (receiving out-of-band signals from the SystemWeaver server). It is possible to switch from the "user" state to the client side due to a call to one of the SystemWeaver server APIs.

-"SyWAPI" status-When a user task needs to interact with the SystemWeaver, it is performed by changing the gap-filling status of a client to "SyWAPI" SystemWeaver API. However, in this state, the processing resource entity can operate in a priority mode. The "SyWAPI" state will be fully operated in the user or task content.

Enter the "SyWAPI" state after calling one of the SystemWeaver APIs. For non-blocking calls, the client-side gap-filling will automatically The "SyWAPI" state returns to the "user" state, but certain accesses (such as those related to signals) can make the user task blocked (the blocked task must wait for some shared system resources) Become available). In this case, the client gap-filling transitions to the "client gap-filling" state.

concept

The following paragraphs discuss the concepts needed to understand the SystemWeaver scheduler.

SystemWeaver memory components

SystemWeaver requires an additional close memory. The use of this memory for the storage of scheduling strategies can give full scheduling modification and adjustment flexibility during the development and processing of the system. The SystemWeaver memory is divided into SystemWeaver Memory Components (WMEs). WMEs are used to represent the task and schedule description items discussed below.

Task description item

The task description item is the key "unit of currency" of the SystemWeaver structure, which represents the unit that competes to access and process the task of the resource entity according to the rules configured in the scheduling hierarchy. The task description item includes:-a reference to a task control block, which sequentially contains a reference to the task to be executed and the data group when it is executed.

-The displacement level, which defines the qualification for the task.

-It can also include synchronous references and timeouts for tasks that will be initially blocked. A more detailed description of the behavior of the blockade mission is beyond the scope of this document.

-A reference to an "Entry Node", which The definition must be added to the scheduling hierarchy part of the task description item (possibly after synchronization).

Scheduling and distribution cone

Two types of allocation cones are used to describe SystemWeaver scheduling behavior: scheduling and allocation cones. The scheduling cone is used to describe a hierarchy of schedulers that gather many "registered" points into a single aggregation point-a many-to-one mapping -. The distribution cone is used to describe a hierarchy of schedulers spreading from a single convergence point to multiple "dispatch" points-one-to-many mapping -.

Scheduling cone

The scheduling cone (shown in red in Figure 5) defines the "application selection node" hierarchy, which is driven by the needs of the application (also shown in the "application schedule" in the preparation state in Figure 2 "Shown). The scheduling cone is a many-to-one mapping, which defines the rules for multi-type tasks and multi-type task entities to compete for system resources.

Distribution cone

The allocation cone (shown in purple in Figure 5) defines the "allocation selection node" hierarchy, which is mainly driven by the attributes of the underlying hardware platform (also shown in the "allocation schedule" in the preparation state in Figure 2 Shown). The allocation cone defines the rules by which the most suitable candidate of the scheduling cone is allocated between the available and appropriate processing resources.

Main scheduling node

There are three main nodes used to describe the scheduling configuration: login node, allocation node, and dispatch node. The main node is an overlap on the potential second node structure, which more closely reflects the detailed implementation of the scheduler.

Login node

The login node defines where to add a new task to the queue. Login nodes are typically many-to-one mapped to distribution nodes, such as the two ends of the same scheduling cone. The login node can be related to a specific task category or based on a strategy derived from other applications. A specific login node can only be mapped to a single distribution node.

Assign node

The distribution node defines the schedule and the contour between the distribution cones. It typically represents a category of processing resources. The scheduling cone typically maps one or more login nodes to a single allocation node, and the allocation cone typically maps a single allocation node to multiple allocation nodes, thus ultimately processing resource entities.

Dispatch node

The dispatch node defines an exit point related to an independent processing resource entity. It will typically utilize the IP cores present in the hardware platform (even though the hardware multi-threaded processor cores can be allocated to multiple dispatch queues) for a one-to-one mapping. Multiple distribution cones can be mapped on independent distribution nodes.

Second schedule node

Define two types of selection nodes: application selection node and distribution selection node. Although application programs and allocation selection nodes are directly mapped on the scheduling layer, they do not completely define the number or types of potential layers in the implementation of the scheduler.

Application selection node

The application selection node defines the transition schedule or the gathering point in the schedule cone. Each application selection node defines a set of optimal candidates that can be A rule of choice.

Assign selection node

When multiple allocation nodes are mapped to a single allocation node, an allocation selection node is required to set a strategy for determining the allocation cone for obtaining access to the processing resource entity.

Schedule configuration

The ready state structure (Figure 2) contains threads that are ready to execute. The overall readiness structure can contain several scheduling and allocation cones. These threads are created with independent thread basic instructions (that is, they are created in the ready state), or they have received the synchronization basic instructions or timed out when they are dependent. The synchronization thread has previously switched from this locked state.

The preparation state structure may contain scheduler node description items and independent thread description items. This structure is mainly defined during system initialization, even if thread description items and their related dynamic scheduler layer description items are allowed to come and go during execution.

The ready state structure allows threads to be scheduled to a processing node or a pool of a specific processing node. This gives load balancing or other allocation behaviors among multiple compatible processing resources, while maintaining the ability to target specific tasks on specific available processing resources (such as hardware accelerators or IO devices).

The scheduling layer is a basic command resource used to implement the main and second scheduling nodes for establishing the readiness structure. The scheduling layer can have a parent, parent or peer relationship with other scheduling layers and task description items.

Figure 6 illustrates a scheduler hierarchical diagram, which shows the master and slave Tie. In this example, y is the main layer of a, b, and c. y is the peer layer of x and z. The main layer can only be the scheduling layer, and the sub-layers can be the scheduling layer or task description items. A specific peer group (for example, a, b, and c) can be composed of a mixture of task description items and scheduling layers. Furthermore, all scheduling layers have a main layer (the dispatch node is the only description item that does not define a main layer).

In the execution process, the main layer can inherit the "metric" (priority, etc.) from the most suitable sub-layer according to the user-defined strategy. This feature can be used when the deep-embedded scheduling strategy has certain knowledge of the most suitable candidates for the compared scheduling branch (this topic will be detailed in the following metric transmission chapter).

The following sections describe the building blocks of any SystemWeaver scheduling hierarchy.

Basic scheduler layer

The scheduler layer defines the hierarchy used to schedule thread description items. Each scheduler layer typically defines a scheduling algorithm, certain metrics used to define scheduling choices, a succession strategy used to define how to pass the metrics from the sub-layer to the main layer, and can be further A list of sub-level elements of the scheduler layer or thread description item. There are three types of scheduler layer description items: root, static and dynamic (where the dynamic layer is a special type of the static scheduling layer). Figure 7 illustrates an exemplary scheduling cone implementation. Figure 36 illustrates the graphical reference legends required for all schedule charts after Figure 4.

Scheduler root description item

The scheduler root description item has a one-to-one mapping with the dispatch queue. It represents the ultimate node in the ready state structure. The root description item metric always contains the succession strategy according to the Construct a copy of the derived metric.

The scheduler root description item is configured during system initialization and always exists.

Static scheduler description item

The static description item of the scheduler exists below the root node in the schedule hierarchy. The main level of static scheduler description items can be other static scheduler description items or root description items. It competes with sibling nodes based on the scheduler algorithm defined by its main layer and its own scheduler metrics.

The static description item of the scheduler is configured during system initialization and always exists. During operation, SystemWeaver maintains the scheduler metrics according to the selection schedule and the metric transfer algorithm.

Dynamic scheduler description item

The dynamic description item of the scheduler exists under the root node in the scheduling hierarchy, and optionally under the static node. The main level of dynamic scheduler description items can be static scheduler description items or root description items. It competes with peer nodes based on the scheduler algorithm defined by its main layer and its own scheduler metrics.

The dynamic scheduler description item can be configured at any time. This allows the system to support much more than the number of scheduling tiers available under a purely static condition. SystemWeaver achieves this effect by increasing the probability that the short-lived demand will be small in a limited period of time even if a large number and variety of threads and dynamic scheduler layers are used in the overall time. For example, in a network system with additional memory that supports up to 4k dynamic components (threads and dynamic scheduler descriptors), 16k connections can be supported at any moment, which is part of the overall connection space The divided data unit is in use in the processor. This flexibility can be achieved with only a small sacrifice in performance. However, if there is no dynamic scheduling description item, it must be created before the child thread description item is added.

During operation, SystemWeaver maintains the scheduler metrics according to the selected scheduling algorithm. In some cases, SystemWeaver will release the dynamic scheduler description item back to the WME idle list.

Processor resource pool

The processor resource pool enables entities of a specific processing resource to be aggregated into a single allocation node. The distribution node can then provide load balancing, smart preemption, and power management among the individual members of the processing resource pool.

Figure 8 illustrates a typical processing resource pool configuration Weaver. Three new definitions of memory components support this processor pool configuration structure:

Pool additional node

The pool attachment node (PAN) is used to attach the scheduler root level to the processor resource pool root level. PANs must exist at the root level of the scheduler (that is, the main level must be a schedule root node). During operation, the PAN metric is automatically updated with a copy of the metric of the pool root node (PRN) inherited from the schedule cone.

The scheduling operator defined in the PANs is not used.

Pool static node

Pool Static Node (PSN) is used to attach the scheduler root level to the processor resource pool root level. It exists in the root layer of the pool (that is, its main layer must be a PAN) and automatically maintains a copy of the metric of the dispatch node (that is, the thread currently executing).

The scheduler operators in the PSN in a particular pool must all be set to the same algorithm, which defines the strategy for selecting the appropriate processing resource entities to be preempted.

Each processing resource pool has a single pool root node (PRN). The root node of the pool defines the allocation node of the processing resource pool. The metrics in the PRNs reflect the optimal threads held in the scheduling cone associated with the allocation node. The PRN main layer indicator must be set to point to one of the static nodes in the pool.

Under normal circumstances, the scheduler algorithm should be set according to the needs of the adjacent layer of the schedule cone.

Dynamic scheduler configuration

SystemWeaver supports the creation and deletion of scheduled nodes during execution, and provides the ability to migrate one task type from one login node to another without loss or disorder. When discussing dynamic scheduler configuration, two additional concepts must be introduced: dormant scheduling layer and marked thread

-The static scheduling layer exists in this hierarchy and can receive push operations (that is, aggregated sub-logging) but cannot be used for scheduling, so it never acts.

-Mark a thread to be scheduled only when it is the last thread dependant on a specific part of the scheduling hierarchy. The number of thread followers on a part of the scheduling hierarchy includes the number of ready threads and the number of blocked threads, and the latter uses this part of the scheduling hierarchy when it becomes ready. The marking thread can carry task references like any other thread, and will typically be used to complete the management of a conversion operation between one part of the scheduling hierarchy and another part.

The following section details an exemplary sequence of conversion of a task stream of a part of the hierarchy. Note that this is a superset for deletion of part of the scheduling hierarchy.

Operation sequence

High-level software is responsible for ensuring that the proper sequence of operations is followed. Failure to observe this order will result in unpredictable behavior. In particular, a new thread must be introduced as part of the scheduling hierarchy into which a marked thread has been inserted.

In this example sequence, it is assumed that a task stream tstream is converted from the scheduler hierarchy h1 to the new scheduler hierarchy h2.

-Create static scheduler hierarchical h2.

-Assign all new task description items on tstream to h2.

-Insert a marked thread into h1.

-Wait for the appearance of the marking thread.

-Wake up the static hierarchical h2.

Scheduler allocation, algorithm, operator and operation domain

Schedule analysis takes many forms (EDF, RMA, etc.) and is typically application-at least section-specific. The result of scheduling analysis is a set of strategies that statically or dynamically control the configuration of the application when it is executed. Through its unique microstructure, SystemWeaver effectively executes these predetermined strategies/algorithms during execution.

Scheduling algorithm

SystemWeaver is used to enable specific algorithms to be defined at silicon design time without disrupting the structure or implementation. However, several algorithms are provided by default: -FIFO scheduling: pure first-in first-out queue.

-Priority scheduling: The most suitable candidate has the highest (increasing priority) or the lowest (decreasing priority) priority metric.

-Round Robin distribution: When a task is extracted from the scheduling hierarchy, the schedule is updated and selected as the next level. Note that the cyclic sort allocation is not a related scheduling strategy that is not in the "leftmost" terminal of a scheduling hierarchy.

-Weighted fair queuing: a complex scheduler in which eligible candidates are selected based on a distribution weight and a certain load measurement (that is, the length of the packet).

By paying attention to the part of the overall scheduler hierarchy, a complex combination of scheduler algorithms can be created to provide precise flow and task management capabilities in the application system.

Operator

The scheduling algorithm is further decomposed into individual scheduling and metric operators, both of which are defined in the main layer node:-Scheduling operator: The operation domain defined in the sub-layer node is used to determine the The most suitable candidate's way. The scheduling operator does not modify the operand in the sub-level node.

-Metric Operator: Define the way in which the operational domain of the most suitable sub-layer is transferred to the main operational domain. The transfer operator can be a null value (do not update the main layer), a copy (overwrite the operation domain of the main layer), or a mathematical function involving one or all of the sublayer and main layer operation domain. In all cases, the sub-layer operating domain is not changed.

The scheduling and metric operators are implemented internally in the SystemWeaver scheduler hardware. A combination of scheduling and metric operators will typically be used to define a specific scheduler algorithm. The scheduler algorithm is generally under a push event (in which a new task is pushed into the scheduler hierarchy) rather than a fetch event (in which a task is extracted from the schedule hierarchy). Refers to different behaviors. For example, consider a FIFO scheduler. When a new task is pushed to a non-empty FIFO scheduling level, the schedule update is not performed; however, when a component is extracted from a FIFO scheduling level, The scheduler must be updated.

Scheduling operator

The scheduling operator is designed to be extensible, but defines a choice of preset operators. The scheduling operator is typically comparative, so the result is always a Boolean value. In the following table, M represents one of the two metrics in the members of a schedule level or the schedule level description item itself, which is based on the following scheme:-Mcurrentn refers to the current most suitable candidate These metrics.

-Mtiern refers to the metrics belonging to the scheduler tier descriptor attached to the current and candidate.

<tables><img file="twi474261b_d0001.tif" he="639" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1871" /></tables><tables><img file="twi474261b_d0002.tif" he="732" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1965" /></tables>

Compound scheduling operators

Mixed scheduling operators are also available, which are the combination of the scheduling operators in the first table. For example: Update Required=(Mcurrent0&gt;Mcandidate0)&amp;&amp;(Mcurrent1&lt;Mcandidate1)

The parameters under discussion can use the metrics in both the main layer and the sub-layer description items. These hybrid operators can be used in both the traditional scheduling layer and the pool allocation layer.

For further information and examples, please refer to the following section of the schedule sequence diagram.

Metric operator

Metric operators are generally arithmetic. As for the scheduling operator is designed to be extensible but has a set of preset operators, see Table 2. The scope of metric operators is complex, ranging from null values or simple copy operations to complex multiplication and accumulation operations.

<tables><img file="twi474261b_d0003.tif" he="513" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="2037" /></tables><tables><img file="twi474261b_d0004.tif" he="731" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="2011" /></tables>

Operand

The scheduling operation domain or metric is divided into two groups:-The regional metric system is related to processing resource entities, scheduler layer and thread description items. The operation of an area measurement automatically generates re-scheduled events.

-The overall metric is selective and is typically related to the state of system resources (certain heuristics such as busy bus or free memory).

A particular scheduling algorithm can use only two metrics, one of which must be regional. The type of the second metric is determined by the MetricllsGlobal flag:-When MetricllsGlobal is reset, metric 1 is regional and will be used as a literal in scheduling operations.

-When MetricllsGlobal is set, metric 1 is an index into the array of the overall metric port.

Area measurement

The task description item and the scheduling layer description item contain two 32-bit operands or scheduling levels. These operational fields are used by their respective main layer in scheduling operations and can be converted and/or transferred to the main layer's operational fields in the scheduling operation For subsequent higher schedules in the hierarchy.

Figure 9 illustrates the amount of displacement expressed in a task description item. In a schedule description item, metric 0 will typically be used to indicate the priority of the task. The least significant byte of this metric is reserved for internal use in the SystemWeaver hardware and client software. There is no such restriction on scheduler level metrics.

Global metrics

The overall metric is generally passive, and a change in the overall metric does not generate repeated scheduling events. On all potentially impacted scheduling resources, the overall metric is asked about some other system events when the scheduling depends on the scheduling resource. Although the SystemWeaver structure does not impose any restrictions on the use of overall metrics, it can be used for system exploration (bus utilization, memory fills up a time pane, etc.), so the rate of change will be relatively low. You can also use filters to average the data.

Scheduling hierarchical configuration details

All configuration diagrams referenced below use a common format as shown in Figure 36.

Figure 10 illustrates the most basic configuration of a single processor, which illustrates the configuration of a single processing resource entity (single dispatch node), along with its necessary scheduling root node. In this simplest case, since there is only a single processor, the scheduling cone is composed of a single FIFO level and the allocation level is empty. Therefore, the scheduler root node is the login node and the distribution node at the same time.

Note that the arrow on the implementation of the scheduling node shown in the figure is from right to left (from the main layer to the sub-layer), which is opposite to the "flow" of the task, which is from the sub-layer Flow to the processor resource entity.

Implement the scheduler in a modular manner and configure it in the dependent memory, which makes the very sophisticated scheduler hierarchy composed of a series of scheduler layers with different strategies, and during the development process Can be adjusted and modified. However, invalid configurations are also possible, and special care must be taken to ensure that appropriate metrics are available for the deep nested scheduler layer.

Inner structure

The scheduling layer stores entries according to the order of arrival or according to a preset FIFO queue strategy. The way the defined scheduling strategy is overlaid on this structure will be described later. New nodes (or description items) are added to the inner structure by a push operation, and removed due to an extraction operation. The scheduled operation does not control the inner link.

Figure 11 illustrates a more representative scheduling structure for a single processing resource entity. From left to right, in this example, two FIFO levels constitute a priority level. There are three scheduling levels in the two levels of the hierarchy. Note that the scheduling layer only has one "leave" node (shown on the right side of the figure), but may have many login nodes (shown on the left side of the figure).

Figure 12 illustrates a detailed diagram of one of the FIFO scheduling layers. This icon illustrates a set of indicators that maintain a list of pairs of links between all peers on the layer. A pair of linked lists is used to maximize the efficiency of removing (extracting) any member of the layer.

Although this detailed illustration only illustrates task description items, the structure is also applicable to any mixed level containing threads and scheduling nodes.

The inner link between peer components is only in the process of pushing and extracting operations Is controlled.

Interlayer structure

In addition to the root layer of the pool, Figure 12 illustrates the structure of the inter-layer connection. Each layer has a master node, which must be either a scheduling root node or a scheduling node. These nodes store an index of the most suitable members of the layer. These child nodes are updated when a scheduling event is received according to the scheduling strategy and the metrics respectively defined in the main node and the child nodes.

Each child node must also refer to its main level.

Root structure of the pool

The root layer structure of the pool is a special case with a single login node and many leaving nodes in one level. The registration node is the point when a scheduling cone gathers (as shown in the "application scheduling" part of the preparation queue structure in Figure 2), and is also called the "allocation node". The "leave node" links the root level of the pool to the "allocation schedule" structure of the processing resource entities that can allocate tasks. Figure 13 illustrates this type of structure for a pool containing two processing resource entities.

Each pool distribution layer must contain a pool root node (PRN) and one or more pool static nodes (PSN), but other node types are not allowed. The PRN contains a reference to the first level of the scheduling cone (stored in the HeadIndex field) and a reference to the first PSN registration to be considered for allocation. A common allocation and metric update strategy must be stored in the scheduler and metric push and fetch operators for each PSN.

Each PSN must refer to the PRM as its sublayer (using the HeadIndex field).

The main layer of a static node in a pool must be an additional node in the pool (PAN). PANs and PSNs must have a one-to-one mapping. However, each processing resource entity may have multiple PANs related to each allocation pool in which it participates. Figure 14 illustrates an exemplary structure in which a processing resource participates in two pools. No restriction is imposed on the number of pools for which a particular processing resource can be a member. Furthermore, any pool can share any number of its constituent processing resources with any number of other pools.

There are two PANs related to each allocation cone in which the processing resource entity participates in the scheduling root node. In addition, there is a scheduling node that provides specific access to the processing resource entity when needed.

The scheduling strategy defined in each PSN of a pool allocation layer defines the method of selecting the most suitable processing resource entity for performing a specific task. For example, one of the strategies may be priority, in which the processing resource entity currently executing the lowest priority task is selected to be preempted when a high priority task arrives from the related schedule.

Figure 15 illustrates a configuration with five processing resource entities and two allocation pools. Note that PRI#3 participates in two sets.

behavior

The following describes the behavior of SystemWeaver scheduling.

General principle

The following provides the most basic background information, which explains the key basic principles of the SystemWeaver scheduling structure.

Indexed queuing

Although the detailed description in Figure 2 has multiple potential queuing points in SystemWeaver, it only uses indicators to achieve it. The queue entity-one SystemWeaver Memory Components (WME)-has never been copied.

Event scheduling

SystemWeaver only updates the schedule selection when a change in the system status requires it. The state change can be divided into three types of events:-A "push event", where the change of the system state causes a new thread description item to be introduced into the ready queue structure (note that this can be a new thread descriptor, Or because the change in the system state has caused the thread to become an existing thread description item for preparation).

-The change in the system state causes a thread description item to be removed from the ready queue structure.

-An "update event" in which the schedule parameter has been modified to require re-evaluation of the schedule selection.

These changes can be:-an interruption (a "push event" due to the block thread related to the interruption being moved to the ready state).

-The arrival of a new task created by an execution task (this can be a push event if the new task is not based on other factors or events).

-A synchronization event-for example, a semaphore signal (assuming a block thread is waiting for the signal, this is a "push event" when the block thread description item is converted to the ready state)

-A change in the execution "priority" of a task, and an "update event".

-The use of a task (transition from preparation to execution) in a processing resource entity (a "extraction event").

-Modification of the displacement level of a task (a "update event").

-A scheduler level scheduling algorithm or metric modification (a "update event").

The system in the ready state SystemWeaver remains idle. In principle, in the most effective power solution, this allows SystemWeaver to be reduced in power and wait for the arrival of an event that requires additional scheduling. Note that changes to the overall metric will not cause rescheduling events.

"Just in time" scheduling

A new entry queued to a specific scheduling level is only compared with the current most suitable entry (identified by the main level HeadIndex). According to the scheduling layer strategy, if it is more suitable than the current title, update the HeadIndex field to refer to the new registration. New logins are always placed behind the current link list structure.

If the scheduling strategy is a FIFO, the HeadIndex indicator will never be updated when a new entry arrives, unless the queue is empty. Therefore, the default behavior is equivalent to a FIFO algorithm when the new login is placed after the queue.

This solution ensures that it takes the least time to process the push operation, which is generally regarded as a delay in scheduling performance. Therefore, extraction scheduling is more onerous in the worst-case scenario where the overall content of a scheduling layer must be evaluated to update the scheduling selection on each extraction operation. However, it is better to always use a regional FIFO algorithm in the physical queue structure, because the modification of the scheduling algorithm does not require the scheduler layer to be reconnected. Furthermore, the extraction schedule can generally be executed along with the execution of the application, so it has a less impact on the overall system performance.

Schedule analysis, strategies and operators

There are several methods of analyzing systems to ensure that the immediate deadline is met, examples of which are EDF (earliest deadline first), RMS (rate monotonic scheduling), and various other stochastic methods. These methods generally tend to be application specific and may be proprietary. However, in all cases, the result of this scheduling analysis is a set of scheduling strategies (ie, priority, FIFO, round-robin sorting, weighted fair queueing). SystemWeaver technology is aimed at the effective real-time execution of the strategies identified by the scheduling analysis. For the configuration in SystemWeaver, each scheduling strategy is further decoded into a set of scheduling operators.

Each scheduler layer has two operators, which are used to determine how the schedule selection is pushed according to one of the scheduling layers (or subordinate ) Is extracted and updated. In some cases, the scheduling operator will require a calculation domain, which is stored in metric fields such as both the scheduler and the task description.

Displacement degree and measurement transfer operator

The amount of displacement can be stored as the information required by the selection scheduling algorithm. The most basic example is priority. In some cases, it is necessary to transfer the metric from the most suitable candidate to the master node, so the information can be used directly in subsequent scheduling selection, or as an operating field in a metric update operation. The metric delivery operator defines how to achieve this result for both push and extraction schemes.

According to the position of the scheduling node in the hierarchy, the metric field can also reflect the priority of the currently executing thread on a specific processing resource. In this case, it is used to determine whether a preemption is required (see the scheduling line below for).

Scheduling resources

The various resources used to implement the scheduling algorithm in execution are described below.

Level

Scheduler layer

A scheduler layer is composed of a main layer-which can be a scheduler root node, a pool root node or a basic schedule node-and several sub-layers, as shown in Figure 6. This sub-layer can be a basic scheduling node, a thread or task description item, or an additional node in the pool. By enabling the sub-level nodes to be the scheduling nodes in their own authority (that is, the main node of the advanced scheduling level), a complex scheduling level hierarchy can be established.

Pool distribution layer

The pool distribution layer may only contain pool root nodes (only one) and pool static nodes. There is only one pool root node for each processing category.

Assignment queue description item-scheduler operator: used to define the scheduling strategy for determining whether the currently executing task should be preempted.

-Measurement transfer operator: There is no measurement transfer operator in a dispatch queue description item.

-Measurement: The measurement element generally stores the measurement of the currently executing thread.

Scheduler and pool root node

-Scheduler operator: used to determine the most suitable candidate for the schedule cone.

-Metric transfer operator: It is always set as the metric of the most suitable candidate to inherit the scheduling cone.

-Metrics: Maintain the metrics of the most suitable candidates for the scheduling cone.

Scheduler level components

-Scheduler operator: used to determine the most suitable sub-candidate of the additional layer.

-Metric transfer operator: defined by the user. Set according to the needs of the subsequent scheduling hierarchy.

-Metrics: user-defined. Set according to the needs of the subsequent scheduling hierarchy. Note that some metric transfer operators will automatically update these fields.

Pool static node

-Scheduler operator: used to determine the most suitable candidate for preemption in a pool allocation layer.

-Measurement transfer operator: used to determine the transfer of the execution task measurement.

-Metric: Set according to the requirements of the pool allocation algorithm. By default, it will reflect the current execution thread measurement; however, a static allocation may be required for a specific allocation strategy.

Pool additional node

-Scheduler operator: Not used.

-Metric transfer operator: used to control the transfer of the optimal task metric.

-Metrics: Metrics used to store the most suitable tasks of the scheduling cone attached to the root node of the relevant pool.

Thread element

-Metrics: used to convey information directly about the suitability of the scheduled task or a scheduler can calculate the suitability.

Scheduling behavior

This scheduling operation is divided into two sub-types:-Standard level scheduling, in which one or more logins in a scheduler layer compete to become the most suitable login in the hierarchy.

-Pool allocation schedule-Identify which one of the processing resource entities chooses should be interrupted.

No scheduled action occurs unless a scheduled event is received.

Schedule push and pull events

As mentioned earlier, a change in system state can generate a "push event" or a "fetch event"-these events cause a rescheduling to occur. All scheduled operations are reserved for work. Only the part of the scheduling hierarchy that can be imagined to be affected by a particular event is re-evaluated, which is said to exist in the re-scheduling range. Figure 17 illustrates the rescheduling range of an event on a basic scheduling hierarchy. Figure 18 illustrates the rescheduling scope of a simple two-entity processing resource pool.

Hierarchical scheduling

Hierarchical scheduling is the most basic building block of the SystemWeaver scheduling algorithm. A scheduling entity can cause a series of hierarchical scheduling operations, as defined by the user-configurable scheduling hierarchy. The result of each level of scheduling operation is the update of the HeadIndex indicator of the main scheduler (a schedule node or one of the scheduler root nodes). The metrics of the master scheduler can also be updated according to the defined metric transfer algorithm.

In principle, the level schedule starts at the current HeadIndex and repeats near the members of the scheduler layer (although in fact, in order to minimize the delay, the push operation only updates the schedule selection for the current headline index), the scheduler The layer establishes whether the HeadIndex needs to be updated according to the following:-The event, which can be a push or extraction operation

-The scheduling algorithm related to the event type (push or withdraw)

-Metrics for members of this level

If one is found to be more suitable for login, the HeadIndex is updated accordingly. Several special cases were discovered to optimize the behavior of this scheduled operation. In all cases the static scheduler layer is ignored in this scheduling operation.

At any time, each scheduling node must know the number of threads or task description items that exist in its sub-hierarchy to ensure that the key fill parameters are maintained. However, it is not always necessary to completely schedule each layer-it is recognized that the immediate downstream rescheduling operation has caused a flag to be updated for a schedule selection update-if necessary, the main layer must also be completely Evaluate; if not needed, there is no need to reschedule the remaining upstream scheduler hierarchy (even if specific other status updates are required).

The last operation in any rescheduling is used to determine whether the optimal preparation task should be allowed to preempt the currently executing task on a specific PRI. The dispatch queue description item contains a scheduling algorithm and a metric of the currently executing task-it can evaluate the scheduler root node metric, and the metric contains a copy of the optimal thread metric of the scheduling cone.

Pool allocation schedule

Pool allocation scheduling only occurs in the pool allocation layer. Due to the basic layer The scheduling seeks to find the most suitable thread/task candidates for execution, and the pool allocation schedule seeks to find the most suitable processing resource entity candidates for preemption. Typically this refers to identifying the processing resource entity that performs the task with the most unsuitable resource pool, and comparing it with the metric of the most suitable'ready' task of the additional scheduling cone.

Although the optimal preparation task has the lowest fitness level compared to all tasks in execution, the remaining allocation cone on each additional processing resource entity is updated to ensure that each scheduling layer maintains an understanding of all accessible downstream tasks. , No further scheduling is required.

Although a preemptive candidate is identified, the schedule update is only passed to the processing resource entity.

Figure 20 illustrates a sequence diagram of rescheduling that occurs due to the push event shown in Figure 18. A basic level scheduling operation occurs at the root level of the pool (level #6) before a pool allocation scheduling operation. In this example, node 5 is selected as suitable for preemption, so the level scheduling operation in level #1 is executed. The subsequent dispatch level scheduling operation causes one of the additional processing resource entities to preempt. Therefore, level #2 is also updated to ensure that the number of downstream tasks/threads is maintained.

Collaboration and preemptive scheduling

The preemptive schedule allows the currently executing task to be inserted asynchronously by a more suitable (higher priority) task. Preemption establishes specific requirements for the execution processing resources and content, such as storage status and the ability to recover once the preemptor has left the resource. Typically, preemptible tasks or threads will maintain the same scheduling suitability through the preparation and execution status.

Conversely, cooperative threads must wait only for a higher priority task It is completed and established. In the SystemWeaver task management solution, the cooperative thread maximizes its suitability when entering the execution state, thereby excluding the existence of a higher priority task and the potential subsequent preemption.

Measure delivery behavior

The transfer of metrics can be caused by a scheduled event or a modification of the metrics of the task or thread in execution.

Scheduled event measurement delivery

When the HeadIndex of the main layer of a scheduling layer is updated due to a scheduling event, the metric is transferred from the optimal grid metric to the main metric according to the hierarchy transfer operator defined in the main layer. These are based on the nature of the operation and the complex scope from a simple copy to a multiple aggregation.

Execution thread measurement transfer

The current metric of threads of execution can be dynamically modified-this can be used to avoid the inversion of priority on blocked resources. When the executing processing resource entity does not participate in an allocation cone, only the dispatch queue description item metric is updated. In the case of an allocation pool, the execution metric is passed to the pool static node related to the processing resource entity (Figure 21). The update of the PSN metric is controlled by the metric transfer operator held in the PSNs themselves. In a specific scheduling scheme, the static value must be kept in the static node of the pool.

In both cases, a rescheduling event is initiated to ensure that the new execution metric does not cause a change in the comparative suitability of the execution and preparation tasks. In the case of the pool, this is only a rescheduling of the scheduler root node metric of the newly executed metric. In the case of the pool, the distribution layer of the pool and all There are subsequent classes that must be re-evaluated.

Idle control

When a processing resource entity enters the idle state, it uses the execution metric to inform the scheduling structure. In essence, an idle processing resource entity is the one who "executes" the lowest possible priority task, and will therefore be preempted by the arrival of any task. The execution metric is set to the idle value to initiate a rescheduling event in a general manner, thus causing the idle task to be "preempted" by the task waiting for the processing resource entity in the ready state structure.

For a more detailed description of the "idle task" and its impact on the power management in the processing resource pool, please refer to the section power management in the following pool scheme section.

Advanced scheduling mode

There can be several advanced modes and behaviors in the interior or it can be achieved by adopting a specific SystemWeaver configuration. The following modes are described in the following sections.

Note that this is not an exhaustive list of available scheduling modes in SystemWeaver.

Timeslicing

Although the SystemWeaver system is event-driven in principle, traditional timer-based systems such as time segments can also be used. Time segment tasks share a processing resource according to individual time segment periods, and it is determined that a task can occupy an interval of processing resources (assuming that no preemptive task becomes ready in this interval).

The time segment task presents a slightly modified "running" behavior to the regular task (as shown in Figure 1). Figure 22 illustrates the progress Two parts of the state: normal and deprecated.

This chapter describes the behavior of the time slice task, along with the rules that must be followed when configuring the task.

SystemWeaver core resources

The following section discusses the resources used to implement the time segment feature in the SystemWeave server core.

counter

A pre-processing resource entity counter is used in the SystemWeaver core to assist time segment behavior. A single per-scaler is also provided, which is provided by the system timer. The bit resolution of the pre-counter is set at the chip design time.

Time slice status indicator

A status bit in the interrupt status register of the pre-processing resource entity is allocated for time segment behavior. This status bit temporarily stores the overdue of the time segment counter and can be used by software to determine whether a time segment event has occurred.

Configuration

All tasks in a time segment group must share the same priority and the same main scheduling layer. Furthermore, time segment tasks should not share the scheduling layer with other non-time segment tasks. The scheduling algorithm of the main layer of the time segment should be set to FIFO. Figure 23 illustrates a typical time segment configuration, in which a time segment group is operated in the background with a foreground group that requires service to obtain priority-an event-driven task.

behavior

When a time segment task is executed first, a system-wide The time segment value is copied to the time segment counter associated with the processing resource entity. This time slice task is said to enter its'normal' execution state (Figure 24). In this normal state, this counter is decreased every cycle. When it reaches zero, the execution priority of the task (stored in the dispatch queue description) is automatically lowered by the hardware, and the task enters the "opposed" state. At this time, the time segment interval counter is switched to the traditional monitoring mode.

In the case that a single processing resource entity provides several time slice tasks, the action of lowering the execution priority (and related rescheduling operations) will cause another member of the time slice group in the ready state structure to be one of the other members of the time slice group. Take up. By querying the time segment status bit, the software client can determine that the time segment process has expired, and push the task currently preempted to the back of the FIFO queue. Therefore, the group complies with the time segment rules of the configuration while maintaining a large amount of SystemWeaver core scheduling and normal operation modes of client behavior.

When a time segment task is preempted by a non-time segment task, even in the "normal" time segment state, the outstanding time segment process is copied to the task control block. The task is then pushed back to the time segment group before the FIFO queue. When the processing of any preemptive task is completed, the time segment task is replied by using the remaining time segment of the preemptive task whose time segment counter is reset.

When a time segment task is preempted in the "opposing" state, it is pushed back to the end of the time segment group FIFO queue. In both cases, the priority metric of the time segment task is maintained at its original configuration value.

When a time segment group is mentioned by a pool of processing resource entities

For (assuming that there is no preemptive task), the login into the "opposed" state does not necessarily cause an immediate switch to another time segment group member. Note the following information: Tp=(t*d)/p where (1pt)

Tready=Tp-d

Tp is the period of a complete cycle (perform each member task once) of a time segment group

Tready The amount of time a specific task waits in the stable state in each cycle

t number of time slice tasks

p The number of resource entities processed in the pool

d The elapsed time of each time segment interval

Note that when p=t, if there is no other preemptive task, the time segment task continues to execute.

Execution profile

The following execution description file illustrates the behavior of SystemWeaver time slices: Figure 25 illustrates a traditional situation with tasks based on a single processor and three time slices. They each share time according to the time segment interval until the preemptive task reaches the position where the time segment task (number 2 in this case) is generated. Once the high-priority preemptive task is completed, the original time segment task reverts to complete the interrupt interval.

Figure 26 illustrates the same solution with two processors. At the beginning, three Time segment tasks are shared between the two processors. When the preemption arrives, the time segment task shares the remaining processors, and when the preemption task is completed, it resumes execution on both processors.

Figure 28 illustrates that when the number of available processing resources is equal to the number of time segment tasks, each time segment task continues to execute on one of the processors. When a high-priority task obtains the control of one of the processors, the time segment group automatically shares the remaining processors according to the defined time segment interval.

Power management in the pool scheme

The preset behavior of a processing resource pool is evaluated by a scheduling selection by a static node of the first pool in a distribution layer. The pool root node (PRN) has a primary indicator, which generally points to the first-level zone static node (PSN) in a distribution layer (Figure 28). When the evaluation is used to preempt one of the candidates, the comparison starts from this login and proceeds around the list using the peer indicator.

If the fitness of all static nodes is the same and the fitness is lower than the candidate of the scheduling cone, the first node encountered will be selected. Therefore, in the low-load scheme, when one or more processors are idle (its metric has been set to the idle value), the processor resource entity closest to the main indicator of the PRN will be preferred to perform new tasks, and The processing resources farthest away from the main indicator will show a long idle period.

Different power saving methods tend to have different impacts when the processing resource must be re-awakened. For example, clock gating can maintain all states in a microstructure, but positive voltage/frequency adjustment can sacrifice all existing when re-awakening. State and presents a poor surge current. There are many different losses in a particular PRI In the case of losing power selection, it makes sense to manage its use based on the time consumption and idleness through the scheduling behavior.

The "idle" state can be divided into multiple sub-states based on the processing resource entity and the capabilities of the system's macro structure. It may be more lossy to restart from a certain state than in other states (for example, a state-maintained clock gating reduces power compared to a power-isolated state). To support these solutions, SysterWeaver supports multiple idle priorities.

For the processing resources with multiple sub-states, the interrupt response can be stably converted back to the idle state when the thread executes a reply. This allows for the progressive introduction of a processing resource into a dynamic set of specific allocations.

example

Figure 29 uses increasing priority to illustrate the "execution priority" of a processing resource entity (PRI) when time passes through an idle state. In the first entity, the idle task sets the priority to its lowest possible setting, which gives the PRI the highest possible chance of assignment to one of the schedulers-compared to its allocation pool peers.

Then the idle task uses a power reduction mode, which may be supported in the processing resource microstructure. Here, the idle task increases the execution priority of the PRI to reduce the possibility of task assignment (PRIs in the previous state will take priority).

Similarly after another period, the idle task (or some other agent) further increases the execution priority (perhaps isolating the power to the PRI-thus avoiding static leakage). The priority adjustment further reduces the PRI suitability of a task assignment-in line with the loss of processing resources that are re-awakened (In this case, surge current, cold cache effect, etc.).

Note: It is not good when the preference of the first login in a distribution layer is pre-occupied. In spite of this situation, a different behavior can be selected when the previous schedule selection becomes the new starting point for the subsequent schedule operation. This choice presents a fairer distribution of high-priority preemptive tasks among processing resource entities in an allocation pool.

Lagging scheduling

In some cases, it is desirable to maintain a scheduling selection, regardless of the absolute correctness of the process. Generally speaking, this situation occurs when the loss of creating a content for a specific type of task or data group is high, and as many tasks as possible should be gathered. Examples of this situation include:-processor cache-a cache that has been filled with a past algorithm or data set will show low attractiveness for a different algorithm and/or data set. This is called a cold cache effect and presents a high percentage of cache misses and results in low performance.

-The FPGA partition can be reset-the resetting of partial execution allows a part of the FPGA to be dynamically reset when the chip is configured and operable, so that different algorithms can be executed in the whole time.

However, the loss of switching from one algorithm to another is high and a larger data set must be gathered to ensure system efficiency.

These two are examples of high-loss content switching.

Delayed scheduling can be used to avoid certain undesirable effects by gathering the loss of content switching operated by multiple users. By using one of the metrics One means that a'system loss' parameter will be able to use lagging scheduling. The hysteresis metric can be based on various measures of loss in the system:-Task memory occupation: where the memory is in a good state, the cumulative footprint of a particular task queue will be used to determine when to schedule the new configuration.

-Processing demand: Among them, it is better to gather the loss of one content during a substantial "active processing" period.

-Time segment: where the time base error (jitter) on the delay is important.

For example, in a situation where FPGA is dynamically reset, a memory can be accumulated on a single part of a configurable structure to multiplex the work of each algorithm content-in this case the memory can occupy A factor in choosing when to re-plan the array. In all cases, it is possible to design a scheduler hierarchy to allow forced switching due to the arrival of high-priority tasks.

The key system level challenges are summarized as follows:-Impact of loss of content switching (switching time, surge current)

-Timing of switching

-How to manage the accumulation of non-active specific content work.

The following describes the possible ways of using SystemWeaver to manage dynamic FPGA configuration. Similar schedule counting and simpler software client side-filling behavior can be used to achieve cold cache management.

FPGA execution period reset

Although it is very similar to processor content switching, it requires several (re)definitions: Configuration-one of a set of programming variables that can be targeted to a specific part of the FPGA structure.

Content switching-the action of changing the configuration of one of the FPGAs that can be reset.

Task-A single unit of work performed by a specific FPGA configuration.

In this proposal, the configuration of the resettable part of the FPGA is regarded as cooperative (as opposed to preemptive), that is, the individual tasks are indivisible and must be completed before a content switch can occur. This ensures that tasks do not need to be re-entered and limits state preservation between contents. The problem is that the number of tasks waiting for a specific configuration must be an integer value. A logical diagram of the management of this outstanding task is shown in Figure 30.

Tasks are organized in queues. These queues always exist; in particular, they accumulate the work of FPGA configuration that is not currently active. The scheduler determines when to switch tasks and manages the execution of tasks in a task group. The resetting supports logic management to re-plan the mechanism of the structure and send a signal when it is completed. According to the collaborative nature of this model, there is no need to retain data in the structure when a content switch is scheduled.

Scheduler

The scheduler performs two distinct functions: -It continuously evaluates the current scheduling options based on the change status of the task queue.

-It manages the execution order of tasks in a task queue.

The arrival of each task causes an update of the schedule selection to ensure the The FPGA structure is in the correct state at any time (greedy scheduling). In the task queue, the scheduler orders the execution sequence according to the characteristics defined by the system structure. The scheduler should at least provide FIFO, cyclic ordering and priority strategies.

Use SystemWeaver's reset management

The SystemWeaver solution provides an outstanding combination of scheduling and internal processor communication capabilities, which can be used to manage parallel execution and internal processing communication during execution. The feature of SystemWeaver can effectively manage tasks and content switching in the traditional instruction group structure, fixed hardware components can reset FPGA blocks, and so on. Figure 31 illustrates an exemplary structure.

SystemWeaver handles the scheduling management of FPGA structure content switching and the task ordering in the individual task queue. Generally speaking, this is in addition to scheduling more typical tasks to the fixed configuration components of the platform.

The reset itself is handled using a specific SystemWeaver hardware client to fill in the gaps. Note that similar scheduling techniques used to manage the "warmth" of the cache do not impose additional requirements on the standard client gap filling. Each scheduled task control block received by the client gap filler is compared with the existing configuration of the structure. If the currently loaded configuration and the scheduled task configuration are different, the client side fills in the gaps and resets the structure without further interacting with the SystemWeaver core. Then the structure update selection is controlled solely by the output sequence of the task according to the domination of the scheduler, and the client side fill can be redesigned to accommodate dissimilar resetting strategies.

Scheduling strategy

The scheduling strategy should be determined by the system designer. However, there must be Must be used to support the key capabilities of this feature. In particular, the scheduler algorithm should be able to exhibit lag-that is, stay on a schedule option until a sufficient loss has been gathered elsewhere to warn of switching to an alternative option.

In the example shown, each "task has a randomly created metric, which is added to the metric representing the aggregation of the task group. When a specific task group is provided to remove a task from the queue, "extract" During operation, this aggregate count is reduced.

When a "push" (a new task arrives) or an "extract" operation occurs, the structure scheduler evaluates the metrics of the currently executing task group for each candidate. According to the algorithm in Figure 32: required update=(Ccandidate&gt;Ccurrent+Hysterisis)

Ccandidate's cumulative task loss in the candidate's scheduling layer

Ccurrent's cumulative outstanding task loss in the currently selected scheduling layer

Hysteresis has been added to avoid the lag of content thrashing

Figure 33 illustrates a scheduling hierarchy that can be selected to implement the algorithm described above. In this case, the metric 1 of the "lag scheduler" stores the lag operation domain. Metric 0 can be used to store the static priority of the lagging group, which is used when scheduling between the lagging group and the preemptive group. The assumption is that there are certain tasks that have sufficient priority to force a content switch.

result

Figure 32 illustrates the conceptual effect of this system. Scheduled output of this task Generally speaking, it is cautiously blocked, and it achieves the maximum use of any specific configuration when managing the impact of system traffic design.

Figure 34 illustrates a simulation of the scheduling algorithm for the presentation. The cumulative task "loss" of each of the waiting four configurations is plotted along with the total sum of all losses ("cumulative"). The selection line indicates the available configurations that the algorithm will select.

Hybrid scheduling algorithm example

Hybrid scheduling operators are useful, for example, when scheduling resource pools in the pool allocation layer. For example, perhaps a subset of the members should only be suitable when the queue of tasks waiting to be processed exceeds a certain threshold.

Consider the situation where three processor resources can be used: a RISC processor and two digital signal processors (DSPs) (Figure 35). Each of these resources can theoretically perform a speech encoding operation, but the DSP device is more efficient. In this case, the RISC processor can be presented in the speech coding pool as shown in the figure, but its suitability for participating in the execution will depend on the depth of the task queue waiting for the function.

In this configuration, the root node metric of the pool can indicate priority, and metric 1 can indicate queue filling. In each of the candidate PSNs, the metric 0 will generally indicate the execution priority of tasks executed on its individual processing resource entities (PRIs). In this case, metric 1 will indicate the queues required to make the relevant PRI suitable for scheduling. In this case, the hybrid scheduling algorithm is: required update=(Mcurrent0&gt;Mcandidate0)&amp;&amp;(Mcurrent1&gt;Mcandidate1)

In the PSNs related to the DSP device, M1 will be set to zero, so the algorithm only makes a decision based on the priority. In the case of the RISC processor, M1 will not be zero, and therefore the queue filling represented by Mcurrent1 must be increased to exceed this value for the RISC processor to participate in the execution of the algorithm.

The following describes a SystemWeaver server with a huge structure or processing level.

As mentioned earlier, the SystemWeaver hardware solution has four components:-The SystemWeaver server core

-The SystemWeaver close memory

-The SystemWeaver debugger

-The SystemWeaver client fills gaps

The overall measurement agent is optional, and is used when the system design needs to include the overall state of the system in the scheduling selection.

Main connection group

Figure 38 illustrates the interface groups found around the core.

To ensure that the SystemWeaver core can be easily integrated, all signals are in the same direction and synchronized with a single clock. The following describes the constituent members of these groups. All signal directions are related to the SystemWeaver core.

System control group

The system control group contains various signals used to ensure the correct operation of the SystemWeaver core. These include system clock, real-time clock and reset signal.

Overall measurement group

In some systems, it is desirable to use specific system metrics in the schedule selection process. These metrics can represent various factors, such as interconnect busyness, cache hit ratio, memory usage, and so on.

Peripheral Disruption Group

The peripheral switch group is composed of a group of switches provided outside the SystemWeaver control system. The signals in the peripheral interrupt group can be driven by, for example, an input interface connected to the external world, or directly by the outside of the SoC device through pins. The number of peripheral interrupt inputs is defined during SoC design.

Internal interrupt group

The internal group is composed of two synchronous interrupt groups provided by the SystemWeaver system and a single group of system debugging signals during execution. The number of each signal in a single group will typically correspond to the number of processing resources in the system and will be defined during SoC design.

Closed Memory Interface Group

This group connects SystemWeaver to its private confidential memory resources. Assume that the additional memory is a synchronous SRAM device. The width n of the address path and the width m of the data path are defined during SoC design.

Interconnection group

The individual interconnection strategy-including protocol and number of layers-must be set at SoC design time. For details of any specific bus interface signal, please refer to the corresponding specific bus implementation.

Debug interface group

For details of the interface of the debugger, please refer to the International PCT Application No. PCT/GB2005/003525 in the joint application, which is incorporated herein by reference.

Tightly Connected Memory (TCM)

SystemWeaver TCM is a standard compiler SSRAM technology provided by various EDA manufacturers. According to the requirements of this application, the TCM contains an integer number of SystemWeaver memory devices (WMEs) defined during SoC design. Each WME uses 256 bits of memory space. SystemWeaver supports up to 65536 WMEs, or a 16Mb memory.

Although the queue description item does use WMEs, the number of WMEs required in a typical system will be determined by the thread support requirements. For example, a system that can simultaneously support 400 threads in the SystemWeaver server will require approximately 128 kb of additional memory.

During SoC design, the memory interface can be modified to simplify the path.

Server core sub-block description

Figure 39 illustrates. These functions of the main logical components of the SystemWeaver server entity are mapped to the structure described in Figure 40. This function is divided between four main internal parallel processing elements, which perform the following functions:-Thread Scheduler Input Manager (TSIM): free list maintenance, WME recovery.

-Thread Scheduler Waiting for Manager (TSPM): Waiting list maintenance, synchronization, and promotion to the ready queue structure. The thread synchronization manager maintains the integrity of the waiting queue structure (insertion and removal).

-Thread Scheduler Output Manager (TSOM): ready to queue dimension Maintenance, dispatching queue maintenance, processing resource power management, and interrupt establishment. Maintain the integrity of the prepared queue structure (insertion and removal).

-Thread Scheduler Scheduling Manager (TSSM): Maintain the scheduling options of each processing resource in the preparation queue structure.

Several additional blocks provide support functions:-Thread Scheduler Memory Manager (TSMM): Gathers access to this additional SystemWeaver memory, which includes both exclusive and locking.

-Thread Scheduler Interruption Manager (TSIC): Converts the system interruption into the basic international synchronization instruction.

-Thread Scheduler Interface Manager (TSIF): Provides interconnection, configuration and execution access to SystemWeaver resources.

Figure 40 illustrates the main sub-blocks of the SysmtemWeaver structure. The following sections detail the interactions within the sub-blocks between these components. Each sub-block presents a set of "public methods" to other sub-blocks, so that each sub-block can instruct its peers to perform operations on the structure that it maintains individually.

When specific conditions can be used to complete a command, the status flag is managed in the sub-block.

The direction of the arrow on the interface diagram of the sub-block indicates the master-ship of the bus and does not reflect the direction of the individual components of the signal group.

State description item behavior

Various description item types are used in the operation of SystemWeaver (for further details, please refer to the International PCT Application No. PCT/GB2005/001154 in the joint application, which is incorporated herein by reference). Most of these description items are stateless, however, thread description items and scheduler descriptions Items can be converted to various states under certain circumstances. This document describes these state transitions and the events that caused the transitions.

Thread description item

There are two kinds of thread description items recognized internally by the SystemWeaver: the standard thread description item and the marked thread description item. The latter is specifically used to remove the scheduling hierarchy process synchronously, while ensuring the integrity and order of the thread description items of the previous schedule.

Figure 41 illustrates the state diagram of the two thread description items and the inner thread through which the thread description items have passed. Note that the new and idle states are intermediate states, which are not directly related to a permanent state in SystemWeaver. A literal state variable does not exist in the thread description item unless the state is represented by several flags. Table 3 illustrates the correlation between the flag state and the state of the thread in Figure 41.

Standard thread description item state description

The following is a brief description of the events and states that caused the entry and departure from it.

new

This new state is temporary. The new thread is imported into the TSIF by a push-independent or thread-dependent command. The two situations are handled as follows:-Independent threads (threads that do not have time or synchronization dependencies) immediately switch to the push state. In this case, the TSIF instructs the TSSM to import the thread into the ready queue structure.

-Dependent threads (threads with a time or a synchronization dependency) are converted to the locked state. The TSIF instructs the TSPM to import the thread appropriately It's time to wait in the queue structure.

Blocked

In the locked state, the thread description item waits for one of an external synchronization and/or an opportunistic synchronization. The blocked thread starts at this TSIF. When receiving the appropriate synchronization, the TPSM switches the thread to the push state and instructs the TSSM to import the thread into the ready queue structure.

Pushed

The threads in the push state are synchronized or originally independent, and the TSPM (dependent thread) and TSIF (independent thread) transfer management to the push state in these individual cases. The TSSM pushes the thread to the ready queue structure and converts the thread to the ready state. Switching to this ready state causes repeated scheduling to occur.

prepare

The thread in the ready state has switched from the push state or has been cleared back into the ready queue structure (by the TSSM). The transition to the ready state always prompts repeated scheduling. The thread can move out of the ready state and enter the extraction state or the flushed state, the latter of which is to go beyond the extraction state to clean up a specific situation in a single operation. The thread transitions to the extraction state when it is nominated as the most suitable candidate scheduled by the TSSM.

Extracted

In the extraction state, the thread has been nominated by the scheduler (TSSM) as the most suitable thread to be processed by a specific processing resource entity or a group of entities, and it is converted to this state by the TSOM. The thread can be converted from the extraction state to the cleanup state or the zombie state: -The TSOM switches the thread to the cleanup state due to repeated scheduling to identify a more suitable thread.

-The TSOM switches the thread to the stalled state due to the start of processing in one of the system processing resource entities. The stalled state maintains the thread description item until it can be idle.

Stagnant

Stuck threads are processed in this TSSM. The existence of the stalled state is used to ensure that all dependencies on a specific thread description item have been removed before the thread is idle. This can be guaranteed once the thread has reached the front end of the TSSM processing queue, so no further processing is required.

Cleaned up

The cleanup thread is handled by the TSSM. The cleanup thread must be re-imported into the preparation queue structure, which causes repeated scheduling operations. Once this is completed, the TSSM transitions the thread back into the ready state.

Free

The idle state is a temporary state, which indicates that the WME used by the thread description item is put back into the idle list.

The following is a brief description of the events and states that caused entry and departure

new

The new state is temporary, and the new marking thread is imported into the TSIF by a push marking thread command. The marking thread always bypasses the blocking state to ensure that any processing that exists in the input and output work queues of the TSPM-which can affect the state of the scheduler layer where the marking thread is finally deleted-is already in the marking thread itself It is done before arrival.

Blocked

The TSPM immediately switches the marking thread to the push state and instructs the TSSM to import the thread into the ready queue structure.

Pushed

The TSSM pushes the marking thread to the ready queue structure and converts the thread to the ready state. Switching to this ready state causes repeated scheduling to occur.

Pushed

The TSSM pushes the marking thread to the ready queue structure and converts the thread to the ready state. Switching to this ready state causes repeated scheduling to occur.

prepare

When the marking thread is imported into the preparation queue structure, it unlocks its immediate main layer. The release of the main scheduling layer is then controlled by the count of the number of dependent threads. When the count of dependent threads in the main layer has reached zero-that is, in SystemWeaver, there is no longer a thread description item that depends on the existence of the main scheduling layer, marking that the thread is only suitable for transitioning out of the ready state.

Similar to the standard thread, the marking thread can switch from the ready state to the fetch state or the cleanup state, the latter being a specific situation that crosses the fetch state to clean up in a single operation. The marked thread transitions to the extraction state when it has been nominated as the most suitable candidate scheduled by the TSSM.

Extracted

Mark the thread in the extraction state that has been nominated by the scheduler (TSSM) as the most suitable thread to be processed by a specific processing resource entity or a group of entities. Note that this scheduling selection is a specific situation, which indicates that the scheduling layer is Empty and no longer Have dependent threads. The marking thread can transition from the extraction state to the cleaning state or the stagnant state:-the marking thread is converted to the cleaning state as a result of repeated scheduling identifying a more suitable thread.

-The marked thread was converted to the stalled state because it started processing in one of the system's processing resource entities.

Stagnant

The processing of the stagnant marking thread is similar to the normal thread description item. The main scheduling layer of the marked thread will also be deleted in this state.

Free

The idle state is a temporary state indicating that the WME used by the thread description item is placed back on the free list.

Scheduler level state diagram

The scheduler layer also has a built-in state. For a static layer that lasts for the execution time of the system, the unique state is active. The remaining state is used by the dynamic scheduling layer, that is, those that come and go during execution. Table 4 presents the correlation between the flag status and the status of the scheduler layer in Figure 42.

Scheduler level description item status description

The following is a brief description of the events and states that caused the entry and departure from it.

new

This new state is temporary. The new scheduler layer is imported into the TSIF by a push independent component during the initial process or during execution.

stationary

In this static state, the scheduler layer is allowed to gather threads and potential additional sub-hierarchies, but will never be scheduled by the TSSM. There are two ways to enter the static state:-A new schedule description item can be created in the static state.

-A scheduling layer can be modified during execution and placed in the static state through a dedicated system command sent via the TSIF.

This static state can only be left by a dedicated system command.

proactive

The scheduler layer in the active state actively participates in scheduling and is locked, meaning that it will not be removed when it becomes empty. The static scheduler will typically be built in this state. The dynamic scheduler is converted to this state by a dedicated system command received through the TSIF. The scheduler layer leaves the active state only when receiving a marked thread, where it enters the "waiting idle" state.

Idle while waiting

The scheduler layer remains in the waiting idle state until the following two conditions are met:-the number of dependent components-which is a count that is measured and referenced by keeping one of the number of description items-becomes zero.

-When the number of sub-components becomes zero.

Free

The idle state is a temporary state indicating that the WME used by the scheduling layer description item is returned to the idle list.

Inner sub-block behavior

The following covers the behavior of SystemWeaver involving multiple sub-blocks.

Dynamically scheduled hierarchical operations

The scheduling hierarchy can be added and removed when the system is running. If the specific user-level program is respected, the SystemWeaver guarantees the integrity of the system and the sequence of thread description items that are converted from one part of the scheduling hierarchy to another. See this for further details.

Dynamic displacement level update

The metric can be updated in a standard or marking thread. The behavior depends on the thread state:-If the thread is in the locked state, an appropriate command is sent to the TSPM. Since the waiting queue is sorted, the thread is removed when the metric is updated and inserted into the queue again to ensure that it reappears in the appropriate position.

-If the thread is in any other permanent state, a command is sent to the TSSM, which performs the metric update and then schedules the appropriate part of the scheduling hierarchy.

TSOM/TSSM interaction for scheduling

The TSOM and the TSSM participate in a part of scheduling thread description items to processing resource entities. Figures 72 and 73 illustrate an exemplary sequence diagram of the interaction between the TSOM and the TSSM.

Inner sub-block structure and behavior

Each sub-block is discussed in the form of its main IO, its peers and the physical interface of the outside world, or its command interface or the command interface can be used. Let the agreement be discussed in the form of the method of calling on the appropriate physical interface.

TSIF-Interface Manager

The interface manager is responsible for directing the execution of the commands received from the interconnection group and assigning them to the other sub-blocks.

The following describes the functional entities that exist in the TSIF, and it is not only a translation of commands for internal use.

structure

The TSIF mainly interprets the commands received on the interconnection interface into one or more internal commands of the remaining sub-blocks. The structure resources existing in the TSIF are described in detail below.

Semaphore area lock

The Sign Area Lock (SRL) provides a resource that can be finely tested and locked by any system resource to obtain exclusive access to a system resource.

It can be used for any number of reasons:

-In order to lock an area of system memory that contains one or more shared resources (such as flag objects, mission control objects, etc.), thereby ensuring integrity.

-Lock the SystemWeaver command interface for a multi-cycle command access.

-Lock the SystemWeaver debug event interface for use in multi-cycle events.

SRLs have two states: locked and unlocked. Reading from SRLs is defined as an attempt to obtain a lock, and writing SRLs is defined as an attempt to unlock. There is no need to lock a specific SRL processing resource entity and release it To be associated. The behavior is described below:-Unlocked. In the unlocked state, a control code is returned from a read from one of the SRLs, which indicates to the reader whether the lock attempt was successful. Writing in this state has no effect.

-Locked: Reading from one of the SRLs in the locked state indicates that the SRL is unavailable. A write releases the SRL.

Command processing

The TSIF destroys the command received from the system into possibly multiple internal commands.

Monitor and time clip support

A dual-mode timer counter is selectively provided to each processing resource entity. The two timer modes are monitor and time segment, and the default mode is monitor.

Monitoring sexual behavior is defined by a monitor cycle and the individual count (Figure 44). The monitor cycle is a stepped down version of the system timer, and the downgrade is defined by a system constant in the silicon design. Figure 46(a) illustrates the behavior of each processing resource entity on each predetermined monitor clock cycle.

-Query the counter of the individual monitor to determine whether a monitor interrupt is suitable.

-Create a monitor interrupt when needed.

The watcher timer count is reset on each control access from the processing resource entity associated with the timer, so that only processing resources that do not access SystemWeaver during the watcher interval experience a watcher switch Off.

The time segment behavior is divided between the TSIF and the TSOM. In this TSIF, the timer allocated to each processing resource can be supported by dedicated time segments. When a time segment interval occurs, an automatic measurement operation is provided in the TSOM (the execution priority is lowered). The processing resource itself is only updated when a standard preemption becomes appropriate due to the automatic metric update.

Figure 45 illustrates the behavior of each system clock cycle of the time segment support logic in the TSIF. Figure 46(b) illustrates the behavior of each processing resource on each cycle of the predetermined time segment clock. Note that when a time segment event has occurred, the timer mode is reverted to the monitor mode.

Interrupt handling

SystemWeaver self-accepts the interrupts originating from the system, the peripheral interrupts, the source interrupts of the system, and the processing resource entity interrupts.

Peripheral interruption

Peripheral interrupts can be masked and limited in the TSIF (edge/level trigger, negative/positive logic, etc.).

Handling resource entity interrupts

Disruption processing resources are provided in the TSIF to provide the following capabilities:-Maintain a discontinuity state, including the source of a discontinuity assertion (preemption, time segment, monitor).

-Masking ability.

A special feature is implemented in the TSIF to automatically switch off on the SystemWeaver command interface. Since the command interface is a common access point for all processing resources in the system, the integrity and efficiency must be maintained hold. For this purpose, SystemWeaver automatically handles the interrupt mask when a processing resource acquires a lock on the SystemWeaver command interface to ensure that the processing resource is not interrupted in this critical coding section.

A counter is maintained for each processing resource entity, which tracks the number of successful SystemWeaver command interface sign area lock requests that have been received. Each lock request increases this count and each unlock decreases it. When the counter is increased from zero, the switch is automatically shielded; and when the count is reduced to zero, the switch is automatically unmasked.

TSIM-Enter the administrator

The input manager manages the WME free list, and processes the extraction request of the TSIF and the push request of various sub-blocks (TSIF, TSPM, TSOM, TSSM).

structure

The TSM only contains one structural entity-the SystemWeaver Memory Element (WME) free list. Figure 48 illustrates the structure of the list.

The free list operates according to a last-in first-out (LIFO) strategy. Each member of the list is of type C_SCHED_ENTRY_FREE and is individually linked using indicators referenced by C_FREE_QUEUE_POINTER_INDEX.

Method interface

In addition to the internal method of link list (getting and setting status), the input manager puts forward the following command on its interface: Push idle index (C_TSIM_CMD_PUSH_INDEX)

Calling end: (TSIF, TSSM, TSOM, TSPM)

The push free index command is used to push a free WME index back to the free list. The parameters are summarized as follows:<img file="TWI474261B_D0005.tif" he="145" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1656" />

Extract free index (C_TSIM_CMD_POP_INDEX)

Calling end: TSIF

The extract free index command is used to extract a free WME index from the free list.

The parameters are summarized as follows:<img file="TWI474261B_D0006.tif" he="252" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1716" />

TSPM-waiting for administrator

The waiting manager manages the blocked task or thread description item and waits for an event: synchronously or according to a timer. The individual waiting list connection is controlled by the user (or controlled by higher-level software), which can represent a sign, a contention domain, a discontinuity, or any combination of these.

structure

The waiting manager includes two main components: a variable number of waiting queues and a timer queue. The waiting queue stores a list of threads waiting to be synchronized by an external event, and the timer queue stores a list of threads waiting for a timeout. A thread description item may and is often a member of the two lists, whereby a thread description item is allowed to wait for an external synchronization event for a limited length of time.

Waiting queue structure

The waiting queue structure in Figure 50 is mainly implemented in the close memory In the body, along with the resources and functions in the TSPM to process its content. The TSPM itself contains a title indicator and several elements that refer to a list of description items in the waiting queue. Each waiting queue contains a list of thread description items, and the number of the waiting queue can be dynamically increased and decreased during execution. All thread description items in the locked state exist in a waiting queue (in contrast to the timer queue, threads appear in this queue only when they have a defined timeout). The use of multiple waiting queues is based on the application and the needs and preferences of the application designer. In addition, the waiting queue can be related to the following:-One log. This may happen when a large number of waiting queues each contain a few threads.

-A contention domain. A contention area is an area where multiple entities compete for the same resource. For example, a process (as opposed to a thread) can be regarded as a contention area.

-Switch off. For the fastest response time, interrupts will typically be grouped into a dedicated waiting queue.

Unlike the timer queue, the waiting queue is based on events only. These events are:-A push event in which a new thread is imported into a waiting queue that already exists or must be created.

-A synchronization event in which one or more threads must be converted to the ready queue structure.

The following describes the behavior in these situations:

Push event

Where the TPSM must be placed on the list on a push event Insert the thread description item (according to a recognition order operator metric [0]). There are two situations that must be considered:-Push to an existing waiting queue

-Push to a new waiting queue

The former case is trivial, and the list is queried in order until an insertion point is found. In the traditional case of increasing power priority, the sorting operator is set to "greater than" (C_PEND_MNGR_PUSH_GTR) and the existing list is searched. The insertion point is defined when the metric [0] of the new thread is greater than the sub-list member metric [0].

When a new waiting queue is needed, the waiting queue insertion occurs immediately before the insertion of the new thread registration.

Synchronization event

Synchronization events can be received from the interrupt controller (TSIC) or through the command interface. Synchronization can occur in two modes:-A literal mode, where the command argument establishes a literal reference to a WME index.

-A correlation mode, in which a correlation is found between a field in the thread description item and a field in the synchronization basic instruction.

In this literal mode, since the index of the thread description item is passed into the instruction, there is no need to find the most suitable candidate. The association pattern requires that the optimal synchronization candidate be discovered first.

The association mode contains three sub-types:-Regular, in which only the most suitable candidate in the specific waiting queue is synchronized.

-Multicast, where all suitable candidates in the particular candidate queue are synchronized.

-Broadcast, where all suitable candidates in all waiting queues are synchronized.

The most suitable candidate is identified by an argument sent with the command and a component identification mark also located in the command. The component identification mark specifies which of the candidate thread description item fields is compared with the transmission argument to identify suitability. In the normal mode, the algorithm continues to repeat in the waiting queue until a suitable candidate is found, where it is removed from the waiting list and from the timer queue when available, and is forwarded to The queue structure should be prepared. For multicast and broadcast modes, this process continues until the waiting queue or each waiting queue respectively becomes empty.

The special situation is related to the removal of members from the timer queue. See the detailed description below.

Timing queue structure and operation

Each new thread imported into the timeout queue initially contains an absolute timeout value. This value can be derived by the interface manager from the 32-bit relative or absolute timeout received with an argument.

The timer queue uses the C_THREAD_PENDING_QUEUE_TIMER_PTR_INDEX to store a list of thread description items in the order of timeout, and the most recent timeout is at the top of the list. Note that these thread description items will also be members of the priority list, as indicated by C_THREAD_PENDING_QUEUE_PRIORITY_PTR_INDEX by the second set of indicators Show. Figure 51 shows the basic structure of the timeout queue. The timeout relative to the timeout of the immediate processor is stored instead of storing the absolute timeout value in the individual thread description item member of the timer queue. This value is stored in a 16-bit field using a floating point representation, where the mantissa of the floating point timer format includes the absolute number of 11 significant bits and a 5-bit exponent. The timeout field of the header element in the timer queue is always copied in the TSPM TimeHeadTimeout register, and then reset.

The operation of the time synchronization structure uses several permanent internal resources:-TimerHeadIndex: a header index of the timer list.

-TimerNumElements: The number of elements in the timer queue.

-TimerHeadTimeout: a snapshot of the timeout of the header element.

-TimeDivider: One of the prescaler of the system clock.

-TimerDividerCounter: One of the countdown resources of this divider.

-TimerCounter: A 32-bit counter resource monotonically increases on each pre-divided clock scale.

-TimerErrorAdjustCounter: A 32-bit counter used to aggregate and accommodate errors.

If the TimerDivider register is set to zero, the timer function is turned off.

Timer queue cycle behavior

Figure 52 illustrates the operations that occur on each pre-scaling clock pulse. The TimerHeadTimeout is not zero when there is no waiting for timer synchronization (the timer queue is in a waiting state), so no action is taken. When TimeHeadTimeout becomes zero and the timer queue is not empty, the system adopts one of two states according to the value of TimerErrorAdjustCounter. If the TimerErrorAdjustCounter is zero, the timeout of the TimerHeadTimeout has occurred in this cycle and a basic timer synchronization command is established, which will eventually result in the extraction from one of the timer queues (and the priority queue for logistic purposes). Immediately thereafter, the TimerErrorAdjustCounter is monotonically increased until it is reset after the processing of the basic instruction of a time event has been completed.

Timer queue event

There are three events that cause the timer queue operation:-One time event basic instruction (C_TSPM_CMD_TIME_PRIMITIVE)

-A thread push event is accompanied by a non-zero timeout (threads with a timeout set to zero are not in the timer queue)

-A non-timer synchronization event that occurs during a logistics implementation that removes a thread from the timer queue.

Figure 53 illustrates a very basic representation of the operation mode of the timeout logic. When in the waiting state, the TimerHeadTimeout is not zero and decreases monotonically according to the pre-divided clock. TimerErrorAdjustCounter is maintained at zero in this state. When the TimerHeadTimeout reaches zero, the header of the timer queue has expired and the FSM transitions to a dynamic state that provides extraction operations. In this state, the TimerHeadTimeout is zero and the TimerErrorAdjustCounter is monotonically increased every cycle. This error count is used to determine whether the time taken to execute a previous timeout event has caused a subsequent timeout event to be suitable. Once no further suitable time-out events occur, the FSM transitions back to the waiting state and the TimerErrorAdjustCounter is reset.

The first one of the potential timer sequence of the derived extraction operation is derived from a reset timeout field in the thread description item (see Figure 52). After that, the TSPM must evaluate whether the subsequent extraction is suitable. For this reason, an additional resource TimerLastError is used to maintain a sum of all accumulated extraction thread description item timeout differences (deltas). On each advanced iteration of subsequent members of the timer queue, the TimerLastError is removed from the TimerErrorAdjustCounter to create a normalized error count that corresponds to the timeout of the new thread description item in the timer queue title compare. If the timeout difference in this thread is less than the normalized error count, the thread descriptiveness should also be extracted. Initially, the TimerLastError is zero, so the thread timeout difference is directly compared with the TimerErrorAdjustCounter. Figure 54 illustrates the previous timer queue structure after the thread 1 timeout has passed and the related fetch operation has occurred. Note that the TimerLastError has been differentially updated by the thread 2, and the process of the extraction operation of the thread 1 means that the thread 2 is also suitable now.

Figure 55 illustrates the state of the queue after the thread 2 is fetched. Note that the thread 2 difference has been added to TimerLastError to build the sum of the thread description item differences and accumulated in an execution. Pay attention to the fetch operation cost on thread 2 It takes a sufficient length of time, so thread 3 is now suitable.

Figure 56 illustrates the state of thread 3 after extraction. In this case, the subsequent thread-thread 4 is not suitable for a fetch, so the state of the timer queue can be returned to waiting. The TimerHeadTimeout must be reset as shown.

Note that when transitioning from a dynamic state back to the waiting state, the TimerHeadTimeout must be reset correctly. This is achieved by removing the difference between the TimerErrorAdjustCounter and the TimerLastError from the difference in the new timing queue header.

When a new thread is imported or pushed to the timing queue, two situations must be considered: a push to one of the titles and a push to the body of the timing queue.

-For the push of one of the headers, the TimerHeadTimeout is simply set to the thread difference. When the queue is non-empty, the old title description item difference is set to the TimerHeadTimeout to check the new thread difference.

-For a push to the body of the timer queue block, the block must search the timer list to identify where to insert the thread description item. The next difference in the list is then adjusted to accommodate the addition of the new thread difference (the new thread difference is removed from the next thread difference).

Extract operation

The extraction operation is handled similarly whether due to a timer or an external event synchronization event. Consider two situations: the thread fetched is at the beginning of the timer queue and not there. In the former case, there are three solutions; where the timer queue is in the waiting state and the timer queue The sequence is in a dynamic state.

-For a fetch operation from the beginning of a'waiting' timer queue, the TimerHeadTimeout is added to the timer difference of the next member of the timer queue to form a new TimerHeadTimeout (note that in the timer extraction The value of TimerHeadTimeout in will always be 0).

-For an extraction operation from the beginning of a "dynamic" timer queue, and the TimerErrorAdjustCounter is greater than the difference in the thread description item of the next time-that is, the next thread is suitable for a timer synchronization, the The error counter-TimerErrorAdjustCounter is reset to the bottom of the difference of the extraction thread.

-For a fetch operation from the beginning of a'dynamic' timer queue, and the TimerErrorAdjustCounter is not greater than the difference in the thread description item of the next time-that is, the next thread is not suitable for a timer synchronization, The difference is reduced by the error counter and the TimerHeadTimeout is updated with the result.

When the extraction thread description item is not at the beginning of the timer list, the difference of the next thread in the timer queue must be reduced by the difference in the thread that is currently removed.

Method interface

In addition to the link list status operations (get and set status) used for waiting and timer queues, the waiting manager indicates the following command on its interface: Synchronization basic command (C_TSPM_CMD_SYNC_PRIMITIVE)

Calling end: TSIF, TSIC

The synchronization basic command command sends a control packet, which releases a blocked thread description item stored in a waiting queue. The argument is explained below:<tables><img file="twi474261b_d0007.tif" he="1253" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1771" /></tables>

Add threads to the waiting queue.

Calling end: TSIF

This command adds a thread description item to a new or an existing work queue. The command is implied to wait for the manager by the existence of a thread description item in the work queue. The following table describes the fields of the thread description item about the command.

<tables><img file="twi474261b_d0008.tif" he="975" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1733" /></tables><tables><img file="twi474261b_d0009.tif" he="432" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1828" /></tables>

Processing marking thread

Calling end: TSIF

This command only sends a marked thread to the work queue of the schedule manager. It is used to ensure that when a marked thread has any possibility of causing a tear-down of a scheduler, all dependent threads have been processed by the waiting manager.

Synchronous basic instructions

Calling end: TSIF

This command sends a synchronous basic command to a specific waiting queue. The following arguments are presented in the command structure:<tables><img file="twi474261b_d0010.tif" he="1280" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1772" /></tables>

Update metrics

Calling end: TSIF

This command updates the metric of a blocked thread and causes a rearrangement of the appropriate waiting queue. If the recognition thread is no longer blocked, the command can be sent to the TSSM. The following arguments are expressed in the command structure.

<tables><img file="twi474261b_d0011.tif" he="154" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1707" /></tables>

Unlock waiting queue

Calling end: TSIF

This command unlocks a waiting queue, so when it becomes empty, it can be released back to the free list. The following arguments are expressed in the command structure.

<tables><img file="twi474261b_d0012.tif" he="154" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1720" /></tables>

TSOM-Output Manager

The output manager manages the dispatch queue structure-which refers to the next execution thread description item-and the execution metrics of the current execution thread.

1.1.1 Structure

The structure of the TSOM is focused on the dispatch queue structure, as shown in Figure 58. The output manager maintains a list of dispatch queue description items, where each DQD is related to a system processing resource entity through the ProcElementID field. There are two groups of components for the DQD, and the DQD closely refers to the function of the TSOM as a whole. The first group-the execution center element-contains the ProcElementID, metric 0, and metric 1, and the preset metric 0 is referenced and managed in the execution state of the task. The second group-the central element of the ready queue-contains the root scheduler index, the preemptive index and the preemptive index refer to the ready queue structure of the thread waiting to be executed. The TSOM also manages the out-of-band signaling (typically a break) to the processing resource entity in the system and the extraction of thread description items from the ready queue structure.

The execution center component

The following is a brief description of the use of the execution center element in the dispatch queue description:-ProcElementID-This is a static field that stores an index of the processing resource entity connected with the dispatch queue description.

-Metrics, 1 is a dynamically updated field, which is used to store the metrics of the currently executing task (including the'idle task' and potential various power reduction states)

-The default metric 0 is a static field used to support an optimization, so that the idle metric can be automatically stored when the currently running thread is pushed back to the SystemWeaver server and thus becomes idle by definition.

The central component of the ready queue

The following is a brief description of the use of the central component of the preparation queue in the dispatch queue description item.

-The root scheduler index is a static reference to the schedule root level related to the dispatch queue.

-The preemptive index is a dynamic field that stores the most suitable candidate for the next execution of a specific processing resource. The preemptive index is completely managed in the TSOM and is set as a result of a dispatch queue event where appropriate.

-The next preemptive index is a dynamic field that stores a main layer of the next most suitable thread in the scheduling hierarchy or the thread index itself. The preemptive index is only set by the TSSM and used as a medium for informing the TSOM of the position in the ready queue structure of the most suitable thread.

Dispatch queue event

The dispatch queue event occurs for two reasons:-Repeated scheduling event: A dispatch queue event occurred in the schedule manager (TSSM) for repeated scheduling operations at any time to identify the status of the dispatch queue. The change-that is, a preemption-is typically due to the processing of a ready queue event (push, fetch or measurement operation).

-A dispatch queue extraction event: the thread index referenced by the preemptive index has been extracted by the interface manager (TSIF). This event is sent to the TSOM by a "dispatch queue extraction" flag (by C_DISPATCH_DESC_POPPED_FLAG) in the dispatch queue description itself.

In the case of a dispatch queue extraction event, the extraction thread transitions to the stagnant state (see Figure 41), and if it does not appear there, it is pushed back to the work queue for the TSSM released. Thereafter, the TSOM hierarchically cuts off the thread from the preparation queue.

For both rescheduling and dispatch queue extraction events, the processing of a dispatch queue event continues to start a repopulation of the preemptive index in the dispatch queue description item. Generally speaking, if the next preemptive index is not a qualified thread index, it is filled in by descending the scheduling hierarchy from the scheduling layer identified by the next preemptive index. Once completed, the identified thread index is placed in the preemptive index field and the thread is virtually extracted from the ready queue, that is, it transitions from the ready state to the extraction state (see Figure 41). This virtual fetch is revealed by locking the optimal thread, marking it as fetched, and adding a flag to return to the TSSM at an event for rescheduling.

Under certain circumstances, a dispatch queue event causes a discontinuity. If the refill preemption index contains a valid thread description item index and the interrupt is enabled Is activated, the interruption of the system processor related to this dispatch queue will be asserted in all situations-unless the early interruption establishment flag is activated and the next preemptive index is a thread, where It will have been established by the TSSM.

The dispatch queue metrics are also updated.

Although the dispatch queue measurement system indicates the suitability of the current execution thread, the dispatch queue system is preempted or a dispatch queue extraction has occurred. Therefore, the thread of execution will be preempted (the worst update of the metric in this case is slightly premature), or a new thread is executing and the dispatch queue metric will be overwritten anyway.

When re-scheduling has occurred and an existing pre-occupied index has been usurp, the existing pre-occupied index must be virtually cleaned back into the preparation queue structure (see Figure 41). In the TSOM, the thread is only marked as cleaned up and pushed back to the TSSM work queue for processing.

If a suitable thread cannot be found, the operation is completed, and the client (processing resource) will be idle under these circumstances.

Set up the dispatch queue fitness measure

The dispatch queue suitability metric reflects the execution priority of tasks currently executed on the processing resource entity indexed by ProcElementID. However, in a specific optimization, the dispatch queue suitability metric can also reflect the execution priority of the task to be executed.

This dispatch queue priority metric is used to control preemption, which operates for a variety of reasons:-Start a new task

-Complete the current mission

-Priority inversion

-Power management

In all cases, the purpose is to adjust the scheduled operation of the preparation queue. When the update results in a modification of the root node of a pool, the node is flagged to the TSSM for repeated scheduling operations. The details of the metric transmission in the pool participants and non-pool participants can be found in the previous section.

As an optimization, when the processing resource entity pushes the currently executing thread back to the ready or blocked state in SystemWeaver. The execution priority is automatically reset to the preset metric.

Method interface

In addition to the basic status operations (getting and setting status) on the link list of the dispatch queue, the output manager indicates the following command on its interface: Automatically execute metric update (C_TSOM_CMD_SERVICE_TIME_SLICE_EXPIRE)

Calling end: TSIF

This command automatically modifies the least significant bit of metric 0 of the metric held in the dispatch queue of the identification processor ID. Since the argument is the processor's identification and not the dispatch queue description item itself, the command starts by stepping through the dispatch queue description item list to find the appropriate description item. The modification is only a simple reversal of the least important bit. Assuming that the reserved part of the metric field is set appropriately, this effect is to reduce the priority of the thread in execution, regardless of whether the priority is raised or lowered of.

The argument is explained below:<tables><img file="twi474261b_d0013.tif" he="256" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1741" /></tables>

Set up dispatch queue metrics

Call drop end: TSIF (from a dedicated system call)

This command sets the execution metrics for a particular dispatch queue. The following arguments are presented in the command structure:<img file="TWI474261B_D0014.tif" he="265" img-content="drawing" img-format="tif" inline="no" orientation="portrait" wi="1686" />

Calling end: TSIF

This command sets the execution metric (0) of a specific dispatch queue to the default value, which is also held in the dispatch queue. There are no arguments for this function.

Dispatch queue events (C_SCHED_ENTRY_DISPATCH_LIST)

Calling end: TSSM

This command causes the dispatch queue description item to be updated when a status change of the preparation queue requires.

TSSM-Schedule Manager

The scheduling manager manages the scheduling options inherent in the main layer and sub-layer links of the preparation queue structure.

structure

The TSSM is a fed command derived exclusively from its work queue interface and is only event-driven. However, the specific behavior is common to several commands. This behavior is described below:

Reschedule

The rescheduling function re-evaluates the scheduling selection of a defined point in the scheduling hierarchy. The rescheduling operation is reserved for the work, no additional work is completed on it, and it is related to the hierarchical part, and the state of the hierarchical structure can be affected by an event.

There is a particularly interesting parameter for this rescheduling function: UpdateRequired. UpdateRequired is used to transfer update status between scheduler layer operations. For example, although other states still need to be managed, a push operation that does not update selections in a sub-layer does not need to cause an overall schedule in the main layer to be repeated. In this case, UpdateRequired may be false.

Figure 60 illustrates a basic flow of repeated scheduling operations. The intratier scheduler (intratierscheduler) executes the scheduling in one layer, and causes the update of the index index of the main layer title. The intertier scheduler scales the subsequent tiers in the scheduling hierarchy toward the dispatch node. Note that the inter-level scheduling function is called with the main index, so that one level of the hierarchy is immediately zoomed. Inter-pool scheduling is a special case scheduling algorithm, which is the only algorithm from a single node, fanout of the root node of the pool to multiple nodes, and static nodes of the pool

The remainder of this chapter describes the operation of the scheduling algorithm.

Inner scheduler

The most basic scheduling operation traverses the linked list of components in a scheduling layer to identify which is the most suitable and update the heading index of the main layer accordingly.

In this common situation, when an appropriate description item is pushed to an empty scheduling layer, the title index and the number of components of the main layer are unconditionally updated and the metric is conditionally transferred from the new sublayer (according to the metric Pass operator) To the main floor.

Figure 61 illustrates a more general situation of a push operation. The suitability of the current selection and the candidate selection are a combination of several factors:-The selection must have content that can be scheduled. This is always true for a thread, but for a scheduler it is based on the content of its subordinate hierarchy.

-If the description item is a scheduler, it must be non-stationary, and its invalid option flag must not be set. .

-If the description item is a standard thread, it must be unlocked, or it must be in a work queue.

-If the description item is a marking thread, the total dependency count of the main layer must be zero, and the marking thread must be the only login remaining in the layer.

Note that the candidate is only compared with the current selection-the best description item derived from a previous scheduling operation. If the candidate defeats the winner, it must be a new winner. As mentioned earlier, the "scheduling pair" is related to the algorithm in the main scheduling layer. The "update main layer" variable carries an instruction back to the caller, and the main layer of this layer should also be updated due to this operation.

In the general case of repeated scheduling, such as when the metric has been updated, or when an extraction has occurred, the entire hierarchy must be updated again to find the new optimal candidate. This process is performed several times through the operation in Figure 61 until the entire hierarchy has been re-evaluated, as shown in Figure 62.

Inter-layer scheduling

The inter-level scheduling is executed once for each scheduler level, and it can be a total of several times for each scheduled event. The scheduling between layers is highly dependent on the type of the main layer. Generalize In other words, the inter-layer schedule continues to call the inner-layer schedule until the main layer becomes a dispatch queue. One exception to this is when encountering a pool allocation node.

Figure 63 illustrates the basic flow of scheduling between layers. There is a unique behavior related to a main level of dispatch queue description item (DQD) and a main level of pool root node (PRN). However, in other cases, the inter-layer scheduler only replaces the current sub-index with the current main layer (in order to repeat the scheduling hierarchy upwards) and re-calls itself.

Figure 64 illustrates the dispatch queue processed in this inter-layer scheduling routine. First, the execution metrics contained in the dispatch queue description item (DQD) are scheduled according to the algorithm defined in the DQD for the metrics contained in the scheduler root node. If this operation determines that a preemption is required, an update to the DQD next preemption index is implemented according to the type of event that starts the rescheduling operation. If this event is pushed by a thread, the scheduled thread index is directly placed in the next preemptive index field, otherwise the scheduler root node index is used. It then falls on the TSOM to repeat the scheduling hierarchy to find the thread description item.

Inter-layer scheduling in the pool

Inter-pool scheduling is used to identify which of the related processing resource entities-if any-should be selected to serve a thread description item in the current pool. In this case it operates in a unique way, since unlike all other scheduling algorithms described here, it typically searches for the least suitable candidate.

Figure 66 illustrates the flow of scheduling operations between layers through a pool, which is graphically represented by Figure 65. The initial inner scheduling operation determines whether the candidate derived from the scheduling hierarchy is more suitable than any one of the tasks to be performed, such as the As indicated by the metric in the static node of the pool in the pool allocation layer. There are two results, an indication of whether an update is needed, and the identification of the node to which the update must be applied.

The algorithm then proceeds to repeat around the overall pool distribution layer, starting at the pool static node indicated by the appropriate "next index" of the root node of the pool.

In each repetition and when managing back office functions (such as thread counter and other state maintenance), call the inter-layer scheduling on the additional layer of the pool. Normally, the inter-layer scheduling continues to advance upwards in the overall scheduling hierarchy until it reaches the dispatch node. Inter-tier scheduling uses an argument "update required", which indicates whether further scheduling tiers should fully re-evaluate the scheduling selection. This flag is set in the content of the pool schedule in two situations:-The static node of the pool currently being processed is recognized by the inner pool schedule as the most suitable thread for processing the optimal thread under the root node of the pool. node.

-The hierarchy below the root node of the pool does not have any suitable scheduling candidates.

Inner pool level scheduling

Figure 67 illustrates the flow of scheduling at the inner pool level. There is an optimization in the first entity that reduces the scheduling time of push only operations-this improves the system's responsiveness to new tasks becoming available.

Assuming that this is not a dedicated push operation, the scheduling operation sets the current selection and candidate selection to the first two PSN nodes in the pool. On each iteration, the current selection is scheduled for the candidate. Note that the same scheduling algorithm is used in the distribution layer of the pool as the other The correct choice in the case is to show the least suitable metric based on a formal standard, so the individual algorithms selected can be different.

If the candidate directs the current selection, that is, the current selection is updated to the candidate, the candidate is updated to the next entry in the layer and the process continues until the candidate becomes the PRN.

Avoid this duplication in a dedicated push operation. The current selection and update node is simply set to the main layer of the PRN (which defines the current scheduling selection), and the candidate is the PRN itself.

In all cases the root node of the pool is then checked for schedulable content, if not, the "no update" status is set and the algorithm returns. However, if there is content that can be scheduled, the process continues to the second stage, whereby the existing choices derived from the PRN (in a dedicated push operation) or the results of the repetition (in other cases) are treated against the PRN itself Schedule it. If the PRN wins the competition, an update is required, otherwise no.

example

Figure 68 illustrates the TSSM scheduler processing related to pushing a thread description item (node #5) to a static scheduling element (node #3). The first inner scheduling operation occurs in the content of the rescheduling function and is related to the master node #3. The rescheduling then moves up one level of the hierarchy and uses the master node #2 to call the inter-layer scheduling. Immediately thereafter, it is time to repeatedly find the master node #1, which is a DQD. Therefore, there is no further call to the inner scheduler and a schedule comparison is completed between the metric of the best candidate stored in the root node and the execution thread stored in the dispatch node. In this case, a preemption is suitable and a dispatch queue event is communicated to the TSOM.

Figure 69 illustrates a more hierarchical scheduling hierarchy. An additional call to the internal scheduling function is created here for the additional level of the hierarchy. Note that even so, the scheduling layers 5 and 3 remain unaffected, because the scheduling events of the rescheduling operation are beyond their scope.

Figure 70 provides a third example, which is a scenario of a pool scheduling operation. As mentioned above, the level in which the thread push event occurs is subject to an inner scheduling operation. In this example, the new thread is most suitable for the root layer of the pool. The inner pool level scheduler then establishes a call to the inner pool level scheduler to determine whether any of the system processing resources should be preempted by the newly arrived thread. In this case, the result of the inner pool level scheduling is that the processing resource entities related to the dispatch queue description item in WME Index 7 should be preempted.

The inner pool layer schedule is then repeated around the pool distribution layer, and the inner layer schedule on node 4 is first called. Then the inner schedule calls the inner schedule to update the scheduler level 1, even if it is not the preemptive layer and does not need to be fully scheduled-the processing is limited to the maintenance of the status information, so there is no queue event for this TSOM. There is no interruption to the processing resources of the system.

This call is the inter-layer schedule on the second layer. In this case, the layer is properly scheduled to establish whether the newly pushed thread description item is more suitable than any other candidate. The candidate metric is finally combined with the executing threads stored in the dispatch queue description item to determine whether a preemption is appropriate. This is true in this example, so a dispatch queue event is sent to the TSOM and the system processing resource entity interrupt is flagged.

Furthermore, only the scheduling layers touched by the scope of the push thread event are re-evaluated.

Method interface

The TSSM is specifically guided through the work queue.

Service thread description item event

Calling terminal: TSIF, TSPM, TSOM

The behavior of this command depends on the setting in the flag of the receiving thread: -If the push or cleanup flag is set, the total thread element count of the main layer is increased. If the extraction flag is set, it is lowered (note that the net effect of one combination can be NULL).

-The thread that has set the push flag is then linked to the ready queue hierarchy. When it has transitioned from the locked state, the main layer count of the dependent thread is also reduced.

-A behavior dedicated to marking threads is the unlocking of the main layer (converting the scheduler layer to the "wait-free" state-see Figure 42).

-The TSSM requested that any thread description items received in the stalled state be released when processing this command.

This command always requests repeated scheduling.

Rescheduling pool distribution layer

Calling end: TSOM

This command is called due to a change in the metrics of an executing thread. When the assignment description item participates in a pool, these metrics are passed through the distribution hierarchy and finally this function is called to re-evaluate the schedule selection.

Reschedule or delete scheduler layer

Calling end: TSOM

This command is called by TSOM for two reasons: -Due to a change in the measurement of an executing thread, the dispatch description item is not involved in a pool, in order to evaluate whether a preemption is appropriate. This operation sends a scheduling root node. When the scheduler contains thread description items in its hierarchy, the schedule is requested again and again.

-In order to delete a scheduling layer, the TSOM is judged to be suitable for this. This determination is based on the lock flag, dependent thread count, and the number of sub-elements (false, 0, and 0, respectively). The virtual release of the description item represents a request for the TSIM.

Push an independent component

Calling end: TSIF

This command can be used in the initialization process to push the static scheduling layer to the scheduling hierarchy, or it can be dynamically used to add thread description items or dynamic scheduling hierarchy during execution.

Update thread metrics

Calling end: TSIF

Update the measurement of a thread description item in the preparation queue hierarchy. Metrics can be updated only when the thread description item is in the ready state (Figure 41)

This command causes repeated scheduling.

Update scheduler status

Calling end: TSIF

This command provides updates to the scheduler algorithm, metric, and metric transfer algorithm. This command caused repeated schedules.

Start the scheduler layer

Calling end: TSIF

This command activates a static scheduler layer. This command caused repeated schedules.

Cancel the scheduler layer

Calling end: TSIF

This command cancels a static scheduler level.

TSMM-Memory Manager

The memory manager (Figure 71) provides multiplexing/de-multiplexing behaviors for gathering access to the TCM. It also provides locking capabilities to ensure the integrity of resources shared among multiple sub-blocks.

structure

From a structural point of view, the memory manager can be mainly regarded as a multiplexing/de-multiplexing, which aggregates the access to the TSM among the six possible requesters. It also maintains the integrity of WMEs, where multiple sub-blocks try to access the same resource by implementing a block cache.

Access aggregation

Access aggregation is controlled by a scheduler. This scheduler is asymmetric:-TSIF has the highest priority

-TSOM has the next highest priority

-All remaining requesters have the same priority and are processed in a job reservation cycle sorting assignment.

Lock cache

Each block has an allocation between one and four locks. These numbers indicate the number of WMEs that the requestor of the sub-block can have exclusive access to. A sub-block that requests a locked resource is blocked until the resource becomes available. The contention between multiple blocks surrounding the same resource is resolved by priority.

Scheduling sequence diagram

Push event

The sequence diagram in Figure 72 illustrates the interaction between sub-blocks after a push event. Note that the task queue has been imported to store commands when the TSSM and TSOM itself are a single thread. Please refer to Figure 68 for a representative scheduling hierarchy.

The state before the push event is the current preemptive index in the thread #4 system dispatch queue description item #1. The first re-schedule identification thread #5 is more suitable than thread #4 because the dispatch queue description item #1 is pushed into the TSOM work queue.

A dispatch queue description item in the TSOM work queue causes a dispatch queue event in the TSOM. This event virtually pushes thread description item #5 and sets the dispatch queue metric accordingly. This push operation causes a status change in the preparation queue, and therefore the schedule must be called again and again. This is achieved by pushing thread #5 to the TSSM work queue for which the push flag has been set.

Since thread #4 was previously pushed virtually, the current phase needs to be cleaned back into the ready queue structure. This also constitutes a status change in the preparation queue structure, and thus requires another re-scheduling. This is achieved by pushing thread #4 to the TSSM preparation queue structure for which the cleaning flag has been set.

Note that the second and third rescheduling operations cannot be combined into the virtual push thread, and the cleanup thread can be located in a large number of areas of the ready queue hierarchy In the other part.

Push event

The sequence diagram in Figure 73 illustrates the interaction between the TSIF, TSOM, and TSSM when a thread description item is pushed from the "virtual" dispatch queue.

The push command itself is received by the TSIF on the command interface or system interconnection. The TSIF sends a dispatch queue push command to the TSOM by pushing the dispatch queue description item to the TSOM that has the push flag set.

The dispatch queue description item in the TSOM work queue causes a dispatch queue event in the TSOM. The dispatch queue event controller indicates the TSSM request thread description item that has just been pushed, in this case thread #5 is placed back on the free list. The next preemptive index of the next best candidate stored for execution is then pushed virtually by the TSOM. This means that a state of the ready queue structure has changed, and thus the TSSM is instructed to be rescheduled by the TSOM-this time a preempt thread is sent to the TSSM work queue that has set the push flag.