# OptScheduling

**Repository Path**: vj_wang/opt-scheduling

## Basic Information

- **Project Name**: OptScheduling
- **Description**: No description available
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2023-11-23
- **Last Updated**: 2024-01-11

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Optimal DAG Scheduler

## DATA

### 数据格式说明

`DAG` 图的相关数据存储在 `data` 目录下

每个文件中可能有多个 `sheet`，每个 `sheet` 代表一个 `DAG`

每个 `sheet` 中有多个 `title`，例如：`Node_Index`、`Node_ID`、`Edges_List`等，详细解释如下：

* `Node_Index`：节点序号
* `Node_ID`：节点名称
* `Edges_List`：本节点所有边的列表，表示方式为：`(1,2);(1,3)`
* `BCET`：最快执行时间
* `AVET`：平均执行时间
* `WCET`：最坏执行时间
* `is_mem`：本 `DAG` 图是否使用内存模型进行问题讨论。如果使用，则为 `"y"`；反之为 `"n"` 或 空
* `node_mem`：节点任务的内存占用（计算过程中的内存峰值）
* `output_mem`：节点任务输出数据的内存占用
* `Prio`：节点任务优先级
* `ProcessorType`：运行本 `DAG` 的异构处理器种类数量。如无此项，则默认在同构处理器上执行任务
* `ProcessorNum`：运行本 `DAG` 的各种处理器数量，表示方式为：`(1,1,1)`
* `ProcessorRun`：节点任务在不同的处理器上运行所需的时间（矩阵）

## Memory model

### 内存模型说明

本项目中将会讨论到 `DAG` 任务运行中使用到的资源消耗，其中一种最常见的就是内存。

根据实际观察，初步设计 `DAG` 任务的内存模型，详述如下。

节点占用内存应该包括 input_mem（大于等于）

## Problem Description

### 问题具体描述

#### 使用 SMT 进行内存受限的异构平台 DAG 任务调度求解的约束讨论

* 约束一：开始时间约束。`DAG` 任务起始节点的开始时间

$$
S_{src} = 0
$$

* 约束二：前驱约束。表示节点之间的依赖关系，节点`i`必须在其所有的前驱节点完成之后才能开始执行，
  即节点`i`的任务开始时间大于前驱节点的完成时间

$$
{\forall}v_i \in V, {\forall}v_j \in pred(v_i), s_i \geq s_j + e_j
$$

* 约束三：处理器约束。映射不超过实际的处理器数量（异构和专用处理器还要加约束）

$$
{\forall}v_i \in V, a_i \geq 0 \wedge a_i < m
$$

* 约束四：内存峰值约束。这也是我们讨论相关问题的新约束，需要所有计算任务运行时，不超过系统内存上限。

那如何判断当前系统中正在占用的内存数据量呢？

**首先**，需要考虑的是正在计算的节点的内存占用。它包括了从前继节点承继下来的输入数据，以及计算过程中需要占用的数据，以及为最终输出数据所作的内存预留

在某一检查时刻 $t$，对于所有任务，当前是否正在执行，可以表示为：

$$
{\forall} v_i \in V, s_i \leq t < s_i + e_i \iff exec_i == 1
$$

若满足上述不等式，则说明当前节点任务正在执行；反之节点任务未执行。具体表示如下：

$$
exec_i = 
\begin{cases}
1,\ v_i\ is\ running\\
0,\ v_i\ is\ not\ running
\end{cases}
$$

**其次**，还需要考虑是否有数据需要暂时留存在内存中（是否有数据被需要）。如果一批输出数据需要被留存在内存中，那么它应该满足：

**前面的节点计算完成，但是后续节点还未开始计算（或已经开始计算但未算完），则需要将数据留存下来**。

在某一检查时刻 $t$，满足：

$$
{\forall} v_i \in V, {\exist} v_j \in succ(v_i),
s_i + e_i \leq t < s_j + e_j \iff mem\_stay_i == 1
$$

$$
mem\_stay_i = 
\begin{cases}
1, \ v_i\ output\ stay \\
0, \ v_i\ output\ not\ stay
\end{cases}
$$

两点之间，前者完成，后面未开始，说明中间这份数据需要留存，将会占用内存。

**第三**，注意到上述表述中都涉及了一个关键的在**检查时刻 $t$**，在具体过程中，该时刻应该如何确定？哪些时刻是需要检查的？

我们认为：**每次添加新任务之前，需要检查，讨论内存限制问题**。即：

$$
t = \{s_i \ | \ {\forall} v_i \in V \}
$$

需要注意的是，在本项目讨论的内存模型中，**节点计算占用内存和数据输出同时存在**

即，内存峰值将会出现在计算节点刚开始的那一刻，此时计算节点需要继承前面节点的输出数据，作为本次计算的输入

还要预留好计算任务过程中将会产生的内存占用，以及输出数据的内存占用（关于内存模型，详见上节）

因此，内存的峰值计算如下：

$$
{\forall} v_i \in V,\ \sum{(exec_i * (node\_mem_i + output\_mem_i))} + \sum{(mem\_stay_i * output\_mem_i)} \leq mem\_bound
$$