<script async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS_CHTML"></script>

<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ]
}
});
</script>

# Real-Time Multiprocessor Scheduling Algorithm Based on Information Theory Principles

- 情報理論原理に基づくリアルタイムマルチプロセッサスケジューリングアルゴリズム

## SECTION I.Introduction

- セクションIはじめに

- Current embedded systems rely on multiprocessor technology to increase their processing capacity due to the computational demand of today’s applications. Despite the advantages of using this type of processing platforms, overcoming the overhead generated by the execution of real-time tasks in multiple processors is an important challenge to acknowledge when implementing solutions for real-time systems. Job migration is a key element to consider when studying this overhead; therefore, current multiprocessor scheduling algorithms are designed to reduce the number of migrations while using the full processing capacity of the system.

- 現在の組み込みシステムは、今日のアプリケーションの計算需要のために、マルチプロセッサテクノロジーを使用して処理能力を高めています。このタイプの処理プラットフォームを使用することの利点にもかかわらず、複数のプロセッサでのリアルタイムタスクの実行によって生成されるオーバーヘッドを克服することは、リアルタイムシステムのソリューションを実装するときに認識すべき重要な課題です。ジョブの移行は、このオーバーヘッドを調査するときに考慮すべき重要な要素です。したがって、現在のマルチプロセッサスケジューリングアルゴリズムは、システムの全処理能力を使用しながら移行の数を減らすように設計されています。

- Multiprocessor scheduling algorithms can be broadly classified as global and partitioned [1]. While a global algorithm allows a task to execute upon different processors at different points in time, a partitioned algorithm restricts each task to execute only on the designated processor. These types of scheduling algorithms have their advantages and disadvantages in terms of the overhead, communication costs, complexity, and the utilization that they can achieve.

- マルチプロセッサスケジューリングアルゴリズムは、グローバルとパーティションに大別できます[1]。グローバルアルゴリズムでは、タスクをさまざまな時点でさまざまなプロセッサで実行できますが、分割アルゴリズムでは、各タスクを指定されたプロセッサでのみ実行するように制限します。これらのタイプのスケジューリングアルゴリズムには、オーバーヘッド、通信コスト、複雑さ、および達成できる使用率の点で、長所と短所があります。

- This letter focuses on the migration minimization problem on global multiprocessor scheduling algorithms. Employing information theory principles [2], we use the information of the task as a parameter to assign jobs’ priorities. To reduce the overhead of using information theory, we propose a simplification method based on the definition of the laxity of a task. Finally, we present the design, implementation, and performance comparison of the proposed multiprocessor scheduling algorithm based on information theory principles with state-of-the-art schedulers. The results of the performance comparison show that our solution is able to reduce the number of migrations, especially on systems with higher utilization per taskset and a higher number of processors, when compared against other global, dynamic-priority, laxity-based algorithms.

- このレターは、グローバルマルチプロセッサスケジューリングアルゴリズムの移行最小化問題に焦点を当てています。情報理論の原理[2]を使用して、タスクの情報をパラメーターとして使用し、ジョブの優先順位を割り当てます。情報理論を使用するオーバーヘッドを削減するために、タスクの緩みの定義に基づいた簡略化方法を提案します。最後に、最新のスケジューラを備えた情報理論の原理に基づいて、提案されたマルチプロセッサスケジューリングアルゴリズムの設計、実装、およびパフォーマンスの比較を示します。パフォーマンス比較の結果は、他のグローバルな動的優先順位の緩やかなベースのアルゴリズムと比較すると、特にタスクセットあたりの使用率が高く、プロセッサの数が多いシステムで、移行の数を削減できることを示しています。

## SECTION II.System Model

- セクションIIシステムモデル

1) Task Model: In this letter, we use a sporadic task model with n independent tasks based on Liu and Layland’s [3] implicit deadline task model. Each job of task τi is characterized by two parameters (ci , ti ), where ci is the worst-case execution time and ti is the minimum interarrival separation time between the jobs of τi . The relative deadline (Di ) of a job of τi is equal to ti and the utilization of a job of τi (Ui ) is equal to ci/ti , where Ui≤1 . We represent the remaining computation time, the remaining time to deadline, and the laxity of a job of τi at time t as ci(t) , Di(t) , and Li(t) , respectively.

- 1）タスクモデル：この手紙では、LiuとLaylandの[3]暗黙の期限タスクタスクモデルに基づいて、n個の独立したタスクを持つ散発的なタスクモデルを使用します。タスクτiの各ジョブは、2つのパラメーター（ci、ti）によって特徴付けられます。ここで、ciは最悪の場合の実行時間で、tiはτiのジョブ間の最小到着間隔時間です。 τiのジョブの相対期限（Di）はtiに等しく、τi（Ui）のジョブの使用率はci / tiに等しく、Ui≤1です。残りの計算時間、期限までの残り時間、および時間tでのτiの仕事の怠惰さをそれぞれci（t）、Di（t）、およびLi（t）として表します。

2) Multiprocessor Platform: We consider a multiprocessor system with m identical processors. The utilization of the system is defined as Usys=∑ni=1ci/ti , where Usys≤m . For the design of our scheduling solution, we assume that there is no overhead when a job is preempted or when a job is migrated to a different processor (interprocessor communication incurs no cost or delay).

- 2）マルチプロセッサプラットフォーム：m個の同一プロセッサを持つマルチプロセッサシステムを検討します。システムの使用率はUsys = ∑ni = 1ci / tiとして定義されます。ここでUsys≤mです。スケジューリングソリューションの設計では、ジョブがプリエンプトされたとき、またはジョブが別のプロセッサに移行されたときにオーバーヘッドがないと想定しています（プロセッサ間通信にコストや遅延は発生しません）。

## SECTION III.Real-Time Scheduling and Information Theory

- セクションIIIリアルタイムスケジューリングと情報理論

- Rincón C. and Cheng [4] presented the mathematical background to measure the information of a task set in a real-time system as well as proposing the relationship between the information of a task and utilization. Based on this letter, we present the following definitions to propose a new scheduling algorithm for multiprocessor systems based on information theory principles.

- RincónC.とCheng [4]は、リアルタイムシステムでタスクセットの情報を測定し、タスクの情報と使用率の関係を提案する数学的背景を示しました。この書簡に基づいて、情報理論の原理に基づいたマルチプロセッサシステム用の新しいスケジューリングアルゴリズムを提案するために、以下の定義を示します。

#### Definition 1:

- 定義1：

- Ptaski(t) is the probability of execution of job from τi at time t , represented by the ratio between the remaining computation time (ci(t)) and the remaining time to deadline (Di(t))

- Ptaski（t）は、残りの計算時間（ci（t））と期限までの残り時間（Di（t））の比率で表される、時間tにおけるτiからのジョブの実行の確率です。

\begin{equation} Ptask_{i}\left ({t}\right )=\frac {c_{i}\left ({t}\right )}{D_{i}\left ({t}\right )}. \end{equation}

#### Definition 2:

- 定義2：

- Usys(t) is the utilization of the system at time t represented by the sum of all Ptaski(t)

- Usys（t）は、すべてのPtaski（t）の合計で表される時間tでのシステムの使用率です。

\begin{equation} U_{\mathrm{ sys}}\left ({t}\right )=\sum \nolimits _{i=1}^{n}Ptask_{i}\left ({t}\right ). \end{equation}

#### Definition 3:

- 定義3：

- NPtaski(t) is the probability of a job from τi (Ptaski(t)) normalized by Usys(t) . We perform this normalization to consider the idle task (Usys<1) . Using (1) and (2) we have

- NPtaski（t）は、Usys（t）で正規化されたτi（Ptaski（t））からのジョブの確率です。この正規化を実行して、アイドルタスク（Usys &lt;1）を考慮します。 （1）と（2）を使用して

\begin{equation} NPtask_{i}\left ({t}\right )=\frac {c_{i}\left ({t}\right )/D_{i}\left ({t}\right )}{\sum _{i=1}^{n}Ptask_{i}\left ({t}\right )}. \end{equation}

#### Definition 4:

- 定義4：

- Itaski(t) is the information of a job from τi at time t . Based on the information theory principles proposed by Shannon [2] and the normalized probability of a job from τi (NPtaski(t)) , we have

- Itaski（t）は、時刻tのτiからのジョブの情報です。 Shannon [2]によって提案された情報理論の原理とτi（NPtaski（t））からの仕事の正規化確率に基づいて、

\begin{equation} Itask_{i}\left ({t}\right )=\log _{2}\left ({1/NPtask_{i}\left ({t}\right )}\right ). \end{equation}

## SECTION IV.Multiprocessor Scheduling Algorithm Based on Information Theory

- セクションIV情報理論に基づくマルチプロセッサスケジューリングアルゴリズム

- Shannon [2] presented the definition of information as a logarithmic function of the inverse probability of occurrence of an event. Based on this definition, he concluded that an event with high information has a low probability of occurrence. Using these remarks, we use the information of a job from τi at time t (Itaski(t)) to assign the priorities of the tasks in the ready queue (the lower the Itaski(t) , the higher the probability of the execution of the task).

- Shannon [2]は、情報の定義を、イベントの発生の逆確率の対数関数として提示しました。この定義に基づいて、彼は情報が多いイベントは発生確率が低いと結論付けました。これらの注釈を使用して、時間tのτiからのジョブの情報（Itaski（t））を使用して、レディキュー内のタスクの優先順位を割り当てます（Itaski（t）が低いほど、実行される可能性が高くなりますタスク）。

- To reduce the number of pre-emptions, our scheduling algorithm allows priority inversion until the first critical moment. We define the critical moment of a job in the ready queue as the scheduling time instant when the task will miss its deadline if it is not executed.

- プリエンプションの数を減らすために、私たちのスケジューリングアルゴリズムでは、最初の重要な瞬間まで優先順位を反転できます。実行可能キューにあるジョブのクリティカルモーメントは、タスクが実行されない場合にタスクが期限を超過するスケジューリング時刻と定義します。

- Observation 1: A job from τi in the ready queue will miss its deadline if it is not executed at time t and Itaski(t)=log2(Usys(t)) .

- 観察1：レディキュー内のτiからのジョブは、時刻tに実行されず、Itaski（t）= log2（Usys（t））である場合、期限に間に合いません。

#### Proof:

- 証明：

- Using (3) and (4), a job from τi with Itaski(t)=log2(Usys(t)) has a ci(t)/Di(t)=1 . Therefore, ci(t)=Di(t) at time t . If this job is not selected for execution, then at time t+1 it will miss its deadline because ci(t)>Di(t) .

- （3）と（4）を使用すると、Itaski（t）= log2（Usys（t））のτiからのジョブには、ci（t）/ Di（t）= 1があります。したがって、ci（t）= Di（t）は時間tにあります。このジョブが実行用に選択されていない場合、時刻t + 1でci（t）&gt; Di（t）であるため、ジョブは期限に間に合いません。

- Based on the previous theory, we present the information-theoretic scheduling algorithm for real-time systems (ITSA-RT). Our algorithm is a dynamic priority, work-conserving scheduling policy based on the lowest Itaski(t) . ITSA-RT is briefly described in Algorithm 1.

- 以前の理論に基づいて、リアルタイムシステム（ITSA-RT）の情報理論的スケジューリングアルゴリズムを示します。私たちのアルゴリズムは、動的優先順位であり、最低のItaski（t）に基づく作業節約型のスケジューリングポリシーです。 ITSA-RTについては、アルゴリズム1で簡単に説明しています。


- In the proposed algorithm, the function reviseTaskInfo will assign a new priority for all the jobs in the ready queue (RQτ) using the value of the information at the current scheduling point t (Itaski(t)) . Then, the taskwithLowestInfo function will select the task to be executed from the active jobs in the system (RQτ and running Task (RUNτ) ). Finally, we calculate the next scheduling point (nextSchedPoint) based on the minimum time value among the task arrivals, task termination, and critical moments, to run the selected task until time t+nextSchedPoint . Our scheduling solution can be easily implemented as a global scheduler for a multiprocessor system with m processors by selecting the first k tasks with the lowest information, where 0≤k≤m .

- 提案されたアルゴリズムでは、関数reviseTaskInfoは、現在のスケジューリングポイントt（Itaski（t））での情報の値を使用して、レディキュー（RQτ）内のすべてのジョブに新しい優先度を割り当てます。次に、taskwithLowestInfo関数は、システム内のアクティブなジョブ（RQτおよび実行中のタスク（RUNτ））から実行するタスクを選択します。最後に、タスクの到着、タスクの終了、およびクリティカルモーメントの最小時間値に基づいて次のスケジューリングポイント（nextSchedPoint）を計算し、時間t + nextSchedPointまで選択したタスクを実行します。私たちのスケジューリングソリューションは、0≤k≤mである最低の情報を持つ最初のkタスクを選択することにより、mプロセッサーのマルチプロセッサーシステムのグローバルスケジューラとして簡単に実装できます。

### A. Reducing the Overhead of Using Information Theory

- A.情報理論を使用するオーバーヘッドの削減

- ITSA-RT uses Itaski(t) to assign the tasks’ priorities by sorting them in an increasing order based on this parameter. The following lemma presents the simplification of the term 1/NPtaski(t) based on (3) and (4), and the definition of laxity of a task.

- ITSA-RTはItaski（t）を使用して、このパラメーターに基づいて昇順にソートすることにより、タスクの優先順位を割り当てます。次の補題は、（3）と（4）に基づく1 / NPtaski（t）の簡略化と、タスクの緩みの定義を示しています。

#### Lemma 1:

- 補題1：

- Minimizing 1/NPtaski(t) is equivalent to minimizing Li(t)/ci(t) .

- 1 / NPtaski（t）を最小化することは、Li（t）/ ci（t）を最小化することと同じです。

#### Proof:

- 証明：

- To simplify the term 1/NPtaski(t) , we consider that Usys(t) is a constant for the jobs of all τi at time t . Therefore, we can reduce our minimization problem by only considering the term Di(t)/ci(t) . Based on the definition of the laxity of a task (Li(t)=Di(t)−ci(t)) , we conclude that Di(t)/ci(t)=Li(t)/ci(t)+1 . Then 1/NPtaski(t) minimization depends on Li(t)/ci(t) .

- 1 / NPtaski（t）の項を簡略化するために、Usys（t）が時間tにおけるすべてのτiのジョブの定数であると考えます。したがって、項Di（t）/ ci（t）のみを考慮することで、最小化問題を減らすことができます。タスクのゆるみの定義（Li（t）= Di（t）−ci（t））に基づいて、Di（t）/ ci（t）= Li（t）/ ci（t）+ １。次に、1 / NPtaski（t）の最小化はLi（t）/ ci（t）に依存します。

- Using Lemma 1, we present a solution to reduce the cost of using the logarithm function at each scheduling point.

- 補題1を使用して、各スケジューリングポイントで対数関数を使用するコストを削減するソリューションを示します。

#### Theorem 1:

- 定理1：

- Itaski(t) can be replaced by Li(t)/ci(t) to assign the tasks’ priorities.

- Itaski（t）をLi（t）/ ci（t）に置き換えると、タスクの優先順位を割り当てることができます。

#### Proof:

- 証明：

- Because minimizing the term 1/NPtaski(t) is equivalent to minimizing Li(t)/ci(t) , and Itaskj(t)<Itaski(t) iff 1/NPtaskj(t)<1/NPtaski(t) , then Itaskj(t)<Itaski(t) iff Lj(t)/cj(t)<Li(t)/ci(t) , for j≠i , 0≤j<n , and 0≤i\<n .

- 用語1 / NPtaski（t）を最小化することは、Li（t）/ ci（t）およびItaskj（t）を最小化することと同等であるため<Itaski(t) iff 1/NPtaskj(t)<1/NPtaski(t) , then Itaskj(t)<Itaski(t) iff Lj(t)/cj(t)<Li(t)/ci(t) , for j≠i , 0≤j<n , and 0≤i\<n .

#### Corollary 1:

- 帰結1：

- ITSA-RT is a zero-laxity-based scheduling algorithm.

- ITSA-RTは、ゼロラクティビティベースのスケジューリングアルゴリズムです。

#### Proof:

- 証明：

- For all the jobs of τi at time t , the priorities will be assigned based on the lowest value of the laxity normalized by the remaining computation time (Li(t)/ci(t)) ; then the highest priority for a job occurs when the laxity is equal to 0.

- 時間tでのτiのすべてのジョブについて、残りの計算時間（Li（t）/ ci（t））で正規化された弛緩度の最小値に基づいて優先順位が割り当てられます。次に、弛緩が0に等しいときにジョブの最高の優先順位が発生します。

### B. Algorithm Design

- B.アルゴリズムの設計

- Based on the previous simplification, we use Li(t)/ci(t) to replace Itaski(t) on the ITSA-RT algorithm. Based on these changes, Algorithm 2 presents the simplified version of the proposed algorithm [simplified information-theoretic scheduling algorithm (SITSA-RT)\].

- 以前の簡略化に基づいて、ITSA-RTアルゴリズムのItaski（t）を置き換えるためにLi（t）/ ci（t）を使用します。これらの変更に基づいて、アルゴリズム2は提案されたアルゴリズムの簡略化されたバージョンを提示します[簡略化された情報理論的スケジューリングアルゴリズム（SITSA-RT）\]。


- At each scheduling point, our solution sets the priorities of the jobs in the ready queue based on the ratio between their laxity and remaining computation time. Then, we select the job with the lowest priority currently running in the system (cpumin ) and the job from the ready queue with the highest priority (maxRQτ ). Finally, SITSA-RT selects the job between cpumin and maxRQτ based on their priorities, before calculating the next scheduling point.

- 各スケジューリングポイントで、このソリューションは、待機時間と残りの計算時間の比率に基づいて、準備完了キュー内のジョブの優先順位を設定します。次に、現在システムで実行されている優先度が最も低いジョブ（cpumin）と、優先度が最も高いレディキューからジョブ（maxRQτ）を選択します。最後に、SITSA-RTは次のスケジューリングポイントを計算する前に、優先度に基づいてcpuminとmaxRQτの間のジョブを選択します。

### 1) Running the SITSA-RT Algorithm:

- 1）SITSA-RTアルゴリズムの実行：

- We present an example task set TS with three periodic tasks τ1=(2,3) , τ2=(2,4) , and τ3=(5,6) , with the same release time (t=0 ) to show the execution of the SITSA-RT algorithm. Based on the utilization of the task set (U=2 ), we need at least two processors to run TS without missing a deadline. Fig. 1 presents the scheduling diagram for the SITSA-RT algorithm.

- 3つの周期的なタスクτ1=（2,3）、τ2=（2,4）、およびτ3=（5,6）を含むタスクセットTSの例を示します。実行を示すために同じリリース時間（t = 0）を使用します。 SITSA-RTアルゴリズムの。タスクセットの使用率（U = 2）に基づいて、期限を逃さずにTSを実行するには、少なくとも2つのプロセッサが必要です。図1に、SITSA-RTアルゴリズムのスケジューリング図を示します。


- For this example, SITSA-RT generates six pre-emptions (τ1,3 at time 8, τ1,4 at time 11, τ2,1 at time 1, τ2,2 at time 6, τ3,1 at time 3, and τ3,2 at time 7), one job migration (τ2,3 ), and twenty six scheduler calls.

- この例では、SITSA-RTは6つのプリエンプションを生成します（時刻8でτ1,3、時刻11でτ1,4、時刻1でτ2,1、時刻6でτ2,2、時刻6でτ2,2、時刻3でτ3,1、およびτ3 、2時間7）、1つのジョブの移行（τ2,3）、および26のスケジューラー呼び出し。

### C. Schedulability Analysis

- C.スケジュール可能性分析

- Based on the zero-laxity condition of SITSA-RT and using the same idea about competing jobs proposed in [5], we present the schedulability analysis of the proposed scheduling solution.

- SITSA-RTのゼロラクシティ条件に基づいて、[5]で提案された競合ジョブについて同じ考え方を使用して、提案されたスケジューリングソリューションのスケジュール可能性分析を提示します。

#### Definition 5:

- 定義5：

- Interj,i(ri,t) is the number of scheduling blocks used by τj (due to its higher priority) in the interval [ri , t ], where ri is the arrival time of τi and i≠j .

- Interj、i（ri、t）は、間隔[ri、t]でτjが使用するスケジューリングブロックの数です（その優先度が高いため）。ここで、riはτiとi≠jの到着時間です。

#### Lemma 2:

- 補題2：

- If the laxity of τi is equal to zero at time t , then the sum of Interj,i(ri,t)∣∀j≠i must be at least m∗(Di−ci) , where ri is the release time of τi .

- τiの緩さが時間tでゼロに等しい場合、Interj、i（ri、t）∣∀j≠iの合計は少なくともm ∗（Di-ci）でなければなりません。ここで、riはτiのリリース時間です。 。

#### Proof:

- 証明：

- Because our algorithm is a work-conserving scheduling policy, the processors do not idle if there are tasks in the ready queue. Assuming that Li(t)=0 , then t =Di−ci(t)+ri . If at time t the sum of all Interj,i(ri,t)∣∀j≠i is less than m(Di−ci) , then τi ’s execution time and blocked time equal to ci−ci(t) and Di−ci−k scheduling blocks, respectively, where k>0 . Therefore, we have that Di(t)=Di− (executed scheduling blocks + blocked scheduling blocks) =Di− ((ci−ci(t) ) + (Di−ci−k ))= ci(t)+k . Then, given that k>0 , we have that Li(t)>0 because Di(t)>ci(t) .

- 私たちのアルゴリズムは作業節約型のスケジューリングポリシーであるため、レディキューにタスクがある場合、プロセッサはアイドルになりません。 Li（t）= 0とすると、t = Di−ci（t）+ riです。時間tですべてのInterj、i（ri、t）∣∀j≠iの合計がm（Di-ci）より小さい場合、τiの実行時間とブロック時間はci-ci（t）とDiに等しい−ci−kスケジューリングブロック、それぞれk&gt; 0。したがって、Di（t）= Di−（実行されたスケジューリングブロック+ブロックされたスケジューリングブロック）= Di−（（ci-ci（t））+（Di-ci-k））= ci（t）+ kです。次に、k&gt; 0とすると、Li（t）&gt; 0になります。これは、Di（t）&gt; ci（t）だからです。

#### Theorem 2:

- 定理2：

- For SITSA-RT to miss a deadline at time t , there must be m +1 tasks with Li(t)/ci(t)=0 .

- SITSA-RTが時間tで期限を逃すには、Li（t）/ ci（t）= 0のm +1タスクが必要です。

#### Proof:

- 証明：

- For a system with m processors, if at time t there are m +1 tasks with Li(t)/ci(t)=0 , then this means that for all these tasks, Li(t) is equal to zero. Therefore, τi will miss its deadline only if there are m tasks with Li(t)/ci(t)=0 , and ∑j≠iInterj,i(ri,t)>m∗(Di−ci) .

- mプロセッサを搭載したシステムの場合、時刻tにLi（t）/ ci（t）= 0のm +1個のタスクがある場合、これはこれらすべてのタスクでLi（t）がゼロに等しいことを意味します。したがって、τ（i）は、Li（t）/ ci（t）= 0でmj≠iInterj、i（ri、t）&gt; m ∗（Di-ci）のタスクがm個ある場合にのみ、期限を逃します。

### D. Performance Comparison

- D.パフォーマンスの比較

- We test the performance of our algorithm against other global, laxity-based, dynamic-priority, multiprocessor scheduling algorithms. We selected the least laxity first (LLF) [6] and the modified LLF (MLLF) [7] because they have the same attributes as SITSA-RT (global, laxity-based, and dynamic priority).

- アルゴリズムのパフォーマンスを、他のグローバルで緩やかなベースの動的優先順位のマルチプロセッサスケジューリングアルゴリズムに対してテストします。 SITSA-RT（グローバル、弛緩ベース、動的優先度）と同じ属性を持っているため、最小弛緩度（LLF）[6]と変更されたLLF（MLLF）[7]を選択しました。

- We use SimSo (a simulation tool to evaluate real-time multiprocessor scheduling algorithms) [8] to implement the SITSA-RT algorithm and to compare its performance with the implementations of LLF and MLLF provided by this simulation tool.

- SimSo（リアルタイムマルチプロセッサスケジューリングアルゴリズムを評価するシミュレーションツール）[8]を使用して、SITSA-RTアルゴリズムを実装し、そのパフォーマンスをこのシミュレーションツールによって提供されるLLFおよびMLLFの実装と比較します。

- We generate the tasksets for our experiments using Staffords randfixedsum algorithm [9], to create unbiased sets of utilization values for any number of tasks and any taskset utilization [10]. We measure the performance of the studied algorithms in terms of the number of pre-emptions, the number of migrations, and the number of scheduler calls for a time period of 1000 time instants. We select as independent variables the number of processors (4, 8, 12, 16), the utilization of the taskset (m * 80%, m * 90%, m * 100%, where m is the number of processors), the number of tasks per taskset (100 tasks) and the number of tasksets per experiment (20 tasksets). To avoid any bias in our analysis regarding the selection of each task period per taskset [10], we use a log-uniform distribution of task periods with values between 10 and 1000 time instants.

- スタッフォードのrandfixedsumアルゴリズム[9]を使用して実験用のタスクセットを生成し、任意の数のタスクと任意のタスクセットの利用率の公平なセットを作成します[10]。調査したアルゴリズムのパフォーマンスは、プリエンプションの数、移行の数、および1000の瞬間におけるスケジューラーコールの数で測定します。独立変数として、プロセッサの数（4、8、12、16）、タスクセットの使用率（m * 80％、m * 90％、m * 100％、mはプロセッサの数）、タスクセットあたりのタスク数（100タスク）および実験あたりのタスクセット数（20タスクセット）。タスクセットごとの各タスク期間の選択に関する分析のバイアスを回避するために[10]、10から1000の瞬間の値を持つタスク期間の対数均一分布を使用します。

- The analysis of the number of migrations (see Fig. 2) shows that this parameter depends on both the utilization and the number of processors. The best performance for the experiment is with 16 processors and 100% utilization (41.21% against LLF and 40.53% against MLLF), while the worst performance is observed for the experiment with 16 processors and 80% utilization (11.15% against LLF and 10.94% against MLLF).

- マイグレーション数の分析（図2を参照）は、このパラメーターが使用率とプロセッサー数の両方に依存することを示しています。実験の最高のパフォーマンスは、16プロセッサと100％の使用率（LLFに対して41.21％およびMLLFに対して40.53％）であり、16プロセッサと80％の使用率（LLFに対して11.15％および10.94％）の実験で最悪のパフォーマンスが観察されます。 MLLFに対して）。


- ！[]（https://i.imgur.com/F0Rs02b.png）

- From this analysis, we can conclude that the performance improvement of SITSA-RT against MLLF and LLF increases for systems with higher utilization per taskset and with higher number of processors.

- この分析から、MLLFおよびLLFに対するSITSA-RTのパフォーマンスの向上は、タスクセットあたりの使用率が高く、プロセッサー数が多いシステムで増加すると結論付けることができます。

- For the number of pre-emptions (see Fig. 3), we see that this parameter only depends on the utilization of the taskset. The best result is for four processors and 100% utilization (15.59% of reduction against LLF and 10.35% against MLLF), while the worst result is observed for 12 processors and 90% utilization (10.72% against LLF and 4.88% against MLLF). The behavior between the performance of LLF and MLLF is a consequence of the mechanism used by MLLF to defer the preemption of the running job as far as the deadlines of other jobs are not missed (allowing priority inversion).

- プリエンプションの数については（図3を参照）、このパラメーターはタスクセットの使用率にのみ依存することがわかります。最良の結果は、4つのプロセッサと100％の使用率（LLFに対して15.59％、MLLFに対して10.35％の減少）であり、最悪の結果は、12プロセッサと90％の使用率（LLFに対して10.72％、MLLFに対して4.88％）です。 LLFとMLLFのパフォーマンス間の動作は、MLLFが使用中のメカニズムの結果であり、他のジョブの締め切りを逃さない限り（実行中のジョブのプリエンプションを延期します（優先順位の逆転を可能にします））。


- Finally, Fig. 4 shows the behavior in terms of the number of scheduler calls. The results show that this parameter is independent of both the utilization and the number of CPUs.

- 最後に、図4は、スケジューラー呼び出しの数の観点からの動作を示しています。結果は、このパラメーターがCPUの使用率と数の両方から独立していることを示しています。


- Table I shows that the number of scheduler calls mainly depends on the number of jobs per taskset. The highest number of scheduler calls is with 16 processors and 90% utilization (highest number of jobs per taskset = 15 546.1), while the lowest number of scheduler calls is observed with four processors and 90% utilization (lowest number of jobs per taskset = 13 673.25).

- 表Iは、スケジューラー呼び出しの数が主にタスクセットごとのジョブ数に依存することを示しています。スケジューラコールの最大数は16プロセッサで90％の使用率（タスクセットあたりのジョブの最大数= 15 546.1）ですが、スケジューラコールの最小数は4プロセッサで90％の使用率（タスクセットあたりのジョブの最小数= 13 673.25）。


- From these results, we can conclude that there is no significant difference between the studied algorithms in terms of the number of scheduler calls. However, it is important to highlight that SITSA-RT generates more scheduler calls than MLLF but less than LLF.

- これらの結果から、スケジューラー呼び出しの数に関して、調査したアルゴリズム間に有意差はないと結論付けることができます。ただし、SITSA-RTが生成するスケジューラー呼び出しは、MLLFよりも多いがLLFよりは少ないことを強調することが重要です。

## SECTION V.Conclusion

- セクションV結論

- In this letter, we have presented a new global, dynamic-priority, laxity-based algorithm based on information theory principles that reduces the number of migrations on multiprocessor systems. We have proposed a simplification method, based on the definition of the laxity of a task, to reduce the overhead generated by using information theory to assign jobs’ priorities. The performance comparison against LLF and MLLF showed that SITSA-RT is able to reduce the number of migrations (up to 41.21%) and the number of pre-emptions (up to 15.59%) while producing a similar number of scheduler calls.

- この書簡では、マルチプロセッサシステムでの移行の数を減らす、情報理論の原則に基づく、動的で優先度が高く、緩やかな新しいグローバルアルゴリズムを示しました。情報理論を使用してジョブの優先順位を割り当てることによって生成されるオーバーヘッドを削減するために、タスクの緩みの定義に基づいた簡略化方法を提案しました。 LLFおよびMLLFに対するパフォーマンスの比較により、SITSA-RTは、同様の数のスケジューラーコールを生成しながら、移行の数（最大41.21％）およびプリエンプションの数（最大15.59％）を削減できることがわかりました。

- An important observation from the experiments is that SITSA-RT is able to schedule all the taskset without missing a deadline. Therefore, we will study the optimality condition of our scheduling solution. Also, even though we are certain that our algorithm has more overhead than LLF and MLLF due to the normalization of the laxity by the remaining computation time, we will analyze how the reduction in the number of migrations affects the performance of SITSA-RT, using WindRiver Workbench. Finally, we will compare the performance of SITSA-RT against other nonlaxity-based multiprocessor scheduling algorithms to measure its performance in terms of the number of migrations.

- 実験からの重要な観察は、SITSA-RTが期限を逃さずにすべてのタスクセットをスケジュールできることです。したがって、スケジューリングソリューションの最適条件を検討します。また、残りの計算時間による弛緩の正規化により、アルゴリズムにLLFおよびMLLFよりもオーバーヘッドが多いことが確実である場合でも、マイグレーション数の削減がSITSA-RTのパフォーマンスにどのように影響するかを分析します。 WindRiverワークベンチ。最後に、SITSA-RTのパフォーマンスを他の非弛緩ベースのマルチプロセッサスケジューリングアルゴリズムと比較して、移行数の観点からパフォーマンスを測定します。