V. Multiprocessor scheduling services

V.1 Global multiprocessor scheduling

V.2 Cache interference analysis

Cache interference in Cheddar is based on the concepts of Cache Related Preemption Delay (CRPD). The bounds on the CRPD are computed by using :
     - Useful Cache Block [LEE 98]
     - Evicting Cache Block[BUS 95]
The following process is required to run the CRPD analyses implemented in Cheddar.

V.3 Memory interference analysis

V.4 Network-On-Chip interference analysis

V.5 Partitionning algorithms

Multiprocessor system is good for heavy computing demands. It is sometimes the only way to provide sufficient processing power to meet critical real-time deadlines. In general multiprocessor systems are also more reliable than uni-processor systems. Scheduling of multiprocessor systems is proven to be a NP-hard (Non-deterministic Polynomial-time) problem [LEU 82]. The complexity class NP is the set of decision problems that can be solved by a non-deterministic machine in polynomial time. The complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. The most common resources are time (how many steps does it take to solve a problem) and space (how much memory does it take to solve a problem). Other resources can also be considered, such as how many parallel processors are needed to solve a problem in parallel. There are many scheduling heuristics to solve this. Rate-monotonic scheduling is good for numerous reasons: Rate-monotonic algorithm is optimal for fixed priority assignment of periodic tasks on a processor so it�s easy to design predictable real-time system. Also it is easy to implement and it takes minimal scheduling overhead.

Cheddar has four algorithms: RMNF, RMFF, RMBF, RMST and RMGT. Each of these are off-line schemes, so the entire task set must be known before starting task assignment. Bounds for functions are calculated using .

Rate-Monotonic-Next-Fit [SON 93]

Upper bound for this algorithm is 2.67. Tasks are sorted in non-decreasing order of periods. Then tasks are placed on processors, according to the IP Condition (Increasing Period). The first task is placed on the first processor. Then the second task is placed on the first processor, if it meets the IP Condition. Otherwise it is placed on a new processor. This continues until all tasks are scheduled.

Rate-Monotonic-First-Fit [SON 93]

The upper bound for this algorithm is 2.33 [SON 93] (original study by Liu and Dhall had a wrong bound of 2.23). Tasks are sorted in non-decreasing order of periods. The IP Condition is used to verify teh schedulability of tasks on processors. The first task is placed on the first processor. Then the second task is placed on the first processor, if it meets the IP Condition. Otherwise it is placed on a new processor. The third task is tried to be placed on the first processor according to the IP Condition. If it does not meet the condition, the task is tried to be placed on the second processor. Otherwise a new processor is selected for the third task�

Rate-Monotonic-Best-Fit [SON 93]

The upper bound for this algorithm is 2.33. Tasks are sorted in non-decreasing order of periods. The first task is placed on the first processor. For the second task, the function checks all processors, whether they meet the IP Condition. For processors that satisfy the condition, the algorithm checks the number kj of tasks already assigned to each processor j, and computes Uj, the total utilization of the kj tasks. And the task is assigned to the processor that has the smallest value. If the condition is not met, a new processor is selected for the task.

Rate-Monotonic Small-Tasks [BUR 94]

The upper bound for RMST is , a = max Ui, i = 1,�,K and U is utilization of all tasks. Tasks are sorted in increasing Si. Si = log2(Ti). The main idea of RMST is to minimize the value of b for each processor. � = max Si � min Si, 1= i =K.

Rate-Monotonic General-Tasks [BUR 94]

The upper bound for RMGT is 1.75. RMGT uses the RMST algorithm for task s = 1/3 and First-Fit heuristics for the rest of the tasks.

Example of use :
  1. First, Define cores for processors. They have to be of Rate Monotonic type.



  2. Second, Define processors for tasks.



  3. Third, Define Address space used by tasks.



  4. Then, Define tasks (host tasks on any processor and address space)



  5. Finally, compute partitioning, with the submenu "Tool/Scheduling/Partition/With Small Task". :









Contact : Frank Singhoff mailto:singhoff@univ-brest.fr
Last update : January, the 4th, 2019