Random DAG Generator

한종우·2021년 1월 21일

Tool

목록 보기

1/5

사담

DAG Task Scheduling 관련 논문을 작성하며 실험을 하는데 있어 Random DAG Generator가 필요했는데, 참고했던 HLBS에서는 TGFF (Task Generator For Free)를 사용했다. 나 역시 기존의 Tool을 사용하면 실험의 타당성이 어느정도 보장되기 때문에 이를 사용하고자 했으나, parameter의 조정에 따른 변화가 manual에 쓰여진 것과 달랐다. 따라서 변인 통제가 잘 되지 않는 것처럼 보였고, 그냥 내가 직접 Generator를 만들기로 했다. 단순하게 만들어서 일반적으로 어떻게 만드는지는 모르겠으나 DAG 구조를 print했을 때 잘 나오기도 했으며 실험 자체도 잘 되는 것으로 보아 사용은 가능할 것 같다. 추후에 visualize하는 것까지 만들면 더 좋을 것 같다. Real-time system에서의 실험을 위한 것이기 때문에 task마다 execution time과 deadline이 존재한다. 원래는 priority나 스케줄 시 할당된 core, finish time 등도 있었으나 Generator와는 별개라고 생각하여 이 repo에는 추가하지 않았다.

사용법

public repo에 있기 때문에 clone 후 바로 사용 가능하다.
아무래도 목적에 따라 task의 attribute 등을 다르게 설정해야 할 것이므로 기본적인 원리가 아래와 같다는 것만 알아두고 나머지는 코드를 수정해서 사용하길 바란다.

git clone https://github.com/Spiraline/DAGGen.git
cd DAGGen
python3 dag_gen.py

파일 형태의 output으로 나오는 것은 아니고 내부의 DAGGen class로 사용가능하다. 필요하다면 파일 형태로 쓰는 것도 추가할 예정이다. (아마 visualize 기능을 추가할 때 같이 하지 싶다.)

설정 가능한 parameter

task_num ([mean, dev]): task의 수를 [mean-dev, mean+dev] 사이의 값으로 설정한다.
depth ([mean, dev]): DAG의 depth를 [mean-dev, mean+dev] 사이의 값으로 설정한다.
start_node ([mean, dev]): start node (entry node)의 수를 [mean-dev, mean+dev] 사이의 값으로 설정한다.
exec_t ([mean, dev]): task의 execution time을 [mean-dev, mean+dev] 사이의 값으로 설정한다.
edge_constraint (bool): True면 outbound_num을 사용하고, False의 경우 extra_arc_ratio를 사용한다.
outbound_num ([mean, dev]): 각 task의 outbound edge를 [mean-dev, mean+dev] 사이의 값만큼 만든다.
extra_arc_ratio (float): extra arc를(task_num) * (extra_arc_ratio) 만큼 생성한다.

leaf node의 deadline은 (level+1) * (exec_t mean) * 2 로 설정된다.

동작 원리

1. Task Initialize

Task class는 아래 값들을 attribute로 갖는다.

tid : task를 식별하는 index
name : 외부에서 task를 식별하는 이름이지만, 알고리즘 내에서는 tid로 주로 식별한다.
exec_t : 실행 시간
parent : 부모 node들의 index를 담은 배열
child : 자식 node들의 index를 담은 배열
isLeaf : leaf node(자식 node가 없는 node)인지 여부를 나타내는 boolean 값
deadline
level : task의 level. 일반적으로는 다음 level의 node로만 edge가 만들어진다.

2. Task의 level 결정

start node의 개수는 고정되어있으므로 먼저 level 0에 해당 개수만큼 start node를 추가한다.
이후 node가 없는 level을 없게 하기 위해 각 level 별로 적어도 하나의 node를 넣어준다. 나머지 node는 임의로 level 0이 아닌 임의의 level에 배정한다.

3. edge 생성

edge_constraint를 사용하지 않는 경우

level 0이 아닌 level에 있는 node들의 경우에는 parent node가 없으면 start node와 같아진다. 이렇게 되면 start node를 정해준 것이 의미가 없으므로, 처음 구현은 parent node는 적어도 1개씩 있도록 하였다. 이는 outbound number의 제한을 고려하지 않았다. 해당 코드는 아래와 같다.

# parent code
for level in range(depth-1, 0, -1):
                for task_idx in level_arr[level]:
                    parent_idx = level_arr[level-1][randint(0, len(level_arr[level - 1])-1)]

                    self.task_set[parent_idx].child.append(task_idx)
                    self.task_set[task_idx].parent.append(parent_idx)

코드에서 확인할 수 있듯 기본적으로 arc는 이전 level로만 이어지는데, 일반적인 DAG들을 만들고자 이후에 level 차이가 1보다 큰 node에 대해서도 extra arc를 만든다. extra arc의 수는 extra_arc_ratio를 통해서 설정 가능하다.

for i in range(extra_arc_num):
                arc_added_flag = False
                while not arc_added_flag:
                    task1_idx = randint(0, task_num-1)
                    task2_idx = randint(0, task_num-1)

                    if self.task_set[task1_idx].level < self.task_set[task2_idx].level:
                        self.task_set[task1_idx].child.append(task2_idx)
                        self.task_set[task2_idx].parent.append(task1_idx)
                        arc_added_flag = True
                    elif self.task_set[task1_idx].level > self.task_set[task2_idx].level:
                        self.task_set[task2_idx].child.append(task1_idx)
                        self.task_set[task1_idx].parent.append(task2_idx)
                        arc_added_flag = True

edge_constraint를 사용하는 경우

for level in range(0, depth-1):
                for task_idx in level_arr[level]:
                    ob_num = rand_uniform(self.outbound_num)

                    child_idx_list = []

                    # if desired outbound edge number is larger than the number of next level nodes, select every node
                    if ob_num >= len(level_arr[level + 1]):
                        child_idx_list = level_arr[level + 1]
                    else:
                        while len(child_idx_list) < ob_num:
                            child_idx = level_arr[level+1][randint(0, len(level_arr[level + 1])-1)]
                            if child_idx not in child_idx_list:
                                child_idx_list.append(child_idx)
                    
                    for child_idx in child_idx_list:
                        self.task_set[task_idx].child.append(child_idx)
                        self.task_set[child_idx].parent.append(task_idx)

outbound number에 제한을 둔 경우에는 level 0부터 시작하여 다음 level의 node로 최대 outbound_num까지의 arc를 만든다. 이 경우 level 0이 아닌 node들에 대해 parent node가 생기지 않을 위험이 있다. 이는 추후에 사용할 일이 더 생기면 개선할 예정이다.