list scheduling algorithm 指令調度 —— 筆記

作者：Yaong
版權：本文版權歸作者和部落格園共有
轉載：歡迎轉載，但未經作者同意，必須保留此段聲明；必須在文章中給出原文連接；否則必究法律責任
 
記錄一下對 list-scheduling algorithm的學習過程。
 
指令調度的一般性目的是為了獲得更快的程式執行速度。
指令調度器需要滿足在執行結果相同的前提下，最小化程式塊的執行時間。
 
指令調度受到三方面的約束，分別是數據的流向，單條指令的執行時間（delay），以及目標處理器的處理能力（多個並行的運算單元）。
數據的流向由DAG圖表示。
 
指令調度需要滿足3個基本要求，我們用n表示DAG中的一個node，S(n)表示節點n被調度到的時鐘周期，delay(n)表示完成執行節點n所需要的時鐘周期數：
1.調度的執行需要在真正執行的開始以後，即S(n) > 0；
2.如果兩個節點(n1,n2)間有一條edge相連接，那麼需要滿足S(n1) + delay(n1) ≤ S(n2)，即如果n2依賴n1的執行結果，那麼n2不能早於S(n1) + delay(n1)前被調度。
3.指令調度器不能調度超過實際處理器單個時鐘周期內能處理的操作類型數。
 
list-scheduling algorithm通過啟發式的方法完成指令的調度。
首先根據需要被調度指令間的依賴關係構建DAG，然後將沒有依賴項的指令加入到active列表中，active列表中的項即為準備好的，可選的被調度指令。
然後，依據一定的等級規則（比如指令的delay周期）從active列表中選擇指令做調度。當一條指令被調度後，需要更新active列表，將不再有依賴項的指令從DAG中加入active列表中。
持續上述過程，直到指令被調度完成。
如果在調度中出現了active列表為空的情況，可能需要插入nop操作。
 
為便於描述，假設以下描述的目標處理器，一次只執行一條三元操作指令。
 
演算法步驟：
  1. 1.構建DAG
  2. 2.計算 Latency
  3. 3.指令調度
 
1、構造DAG
DAG構造需要分析數據流依賴關係。
三種依賴關係：
  1. flow dependence or true dependence
  2. antidependence
  3. output dependence
 
DAG中的edge表示數據的流向，DAG中的node代表一種operation。
每個node都有兩個屬性，分別是操作類型和執行該操作所需要的指令周期。
如果兩個nodes，n1和n2間通過一條edge相連接，說明在n2中會用到n1的執行結果。
 
我們通過如下3個結構體來表示dag，dag_node，dag_edge：
 
struct dag_edge {
   struct dag_node *child;
   /* User-defined data associated with the edge. */
   void *data;
};
 
struct dag_node {
   /* Position in the DAG heads list (or a self-link) */
   struct list_head link;
   /* Array struct edge to the children. */
   struct util_dynarray edges;
   uint32_t parent_count;
};
 
struct dag {
   struct list_head heads;
};
 
首先我們需要初始一個dag，通過dag_create()來完成，struct dag中是一個鏈表頭，通過這個雙向鏈表，將所有待調度的指令連接起來。
 
struct dag *
dag_create(void *mem_ctx)
{
   struct dag *dag = rzalloc(mem_ctx, struct dag);
   list_inithead(&dag->heads);
   return dag;
}

 

根據當前需要調度的指令數來，初始化node，如前文所述，單條指令即為一個node。
使用函數dag_init_node()完成對一個node的初始化，並將該node節點加入到dag鏈表中。
struct dag_node中的成員struct util_dynarray edges表述該node到其他node的edges集合，其是通過動態數組實現的。
 
/**
* Initializes DAG node (probably embedded in some other datastructure in the
* user).
*/
void
dag_init_node(struct dag *dag, struct dag_node *node)
{
   util_dynarray_init(&node->edges, dag);
   list_addtail(&node->link, &dag->heads);
}

 

假設我們有N調指令需要調度，在調用執行 dag_create()、dag_init_node()會形成如下所示的結構，即所有node加入到dag的鏈表中。
 
EXAMPLE:
struct dag_node node[N];
struct dag *dag = dag_create(NULL);
 
for ( int i = 0; i < N; i++) {
    dag_init_node(dag, &node[i]);
}
 
Map:
    dag->heads <--> node[0] <--> node[1] <--> node[3] <--> ... <--> node[N]

 

完成了dag和node的初始化後，接下來需要依據nodes間的依賴關係構建edge，最終形成指令間的DAG。
函數dag_add_edge()實現了從parent向child添加一條edge的操作。
edge通過sruct  dag_edge表示，其用於指向child這個node和特定data。
 
函數dag_add_edge()兩個參數parent和child代表兩個node，完成添加後會有一條邊由parent流向child（parent –> child）。
首先，函數函數dag_add_edge()中判斷，節點parent已有edge指向child，有則退出函數。否則先將該node從dag header中移除，再將child加入到parent的edges所在的動態數組中，並對child->parent_count++，即依賴計數增加1。
 
根據需要調度指令間的依賴關係，依次調用函數dag_add_edge()後，依然留在dag header中的指令，即為沒有依賴項的，準備好了的可調度指令。
 
/**
* Adds a directed edge from the parent node to the child.
*
* Both nodes should have been initialized with dag_init_node().  The edge
* list may contain multiple edges to the same child with different data.
*/
void
dag_add_edge(struct dag_node *parent, struct dag_node *child, void *data)
{
   util_dynarray_foreach(&parent->edges, struct dag_edge, edge) {
      if (edge->child == child && edge->data == data)
         return;
   }
   /* Remove the child as a DAG head. */
   list_delinit(&child->link);
 
 
   struct dag_edge edge = {
      .child = child,
      .data = data,
   };
 
 
   util_dynarray_append(&parent->edges, struct dag_edge, edge);
   child->parent_count++;
}

 

依據依賴關係構建完DAG後，依舊留在dag->heads中的node就構成了active list。
在開始指令調度前，需要計算出DAG中node的Length of the longest (latency) chain，以下簡稱latency。
latency的計算是自底向上的遍歷各個node，具體計算單個node的delay是通過函數dag_traverse_bottom_up()的回調函數介面實現的，這個需要根據實際的指令集來計算。
 
struct dag_traverse_bottom_up_state {
   struct set *seen;
   void *data;
};
 
static void
dag_traverse_bottom_up_node(struct dag_node *node,
                            void (*cb)(struct dag_node *node,
                                       void *data),
                            struct dag_traverse_bottom_up_state *state)
{
   if (_mesa_set_search(state->seen, node))
      return;
 
   util_dynarray_foreach(&node->edges, struct dag_edge, edge) {
      dag_traverse_bottom_up_node(edge->child, cb, state);
   }
 
   cb(node, state->data);
   _mesa_set_add(state->seen, node);
}
 
/**
* Walks the DAG from leaves to the root, ensuring that each node is only seen
* once its children have been, and each node is only traversed once.
*/
void
dag_traverse_bottom_up(struct dag *dag, void (*cb)(struct dag_node *node,
                                                   void *data), void *data)
{
   struct dag_traverse_bottom_up_state state = {
      .seen = _mesa_pointer_set_create(NULL),
      .data = data,
   };
 
   list_for_each_entry(struct dag_node, node, &dag->heads, link) {
      dag_traverse_bottom_up_node(node, cb, &state);
   }
 
   ralloc_free(state.seen);
}

 

完成latency的計算，就要進行指令的調度了。
當前可選的指令處在dag->heads的列表中，即為active list。
從active list中挑出一條指令的規則，一般會通過一個clock來計數當前的執行周期，並根據實際的目標處理器的特點來構建。
當我們從active list中挑出一條具體的指令後，需要將該指令從active list中移除，並且更新active list。因為當一條指令被調度後，對其依賴的指令，如果沒有其他依賴的指令沒有被調度，那麼該依賴的指令需要加入到active list中，該操作由函數dag_prune_head()完成。
 
函數dag_prune_head()首先將被調度的node從dag->heads中移除；然後依次遍歷該node的每條edge所指向的node，遍歷到這些nodes後，將他們的依賴計數進行更新（減一），如果更新後node的依賴計數等於零，說明該node的依賴項均已被調度，該node會被加入到active list（dag->heads）中。
 
/* Removes a single edge from the graph, promoting the child to a DAG head.
*
* Note that calling this other than through dag_prune_head() means that you
* need to be careful when iterating the edges of remaining nodes for NULL
* children.
*/
void
dag_remove_edge(struct dag *dag, struct dag_edge *edge)
{
   if (!edge->child)
      return;
 
 
   struct dag_node *child = edge->child;
   child->parent_count--;
   if (child->parent_count == 0)
      list_addtail(&child->link, &dag->heads);
 
 
   edge->child = NULL;
   edge->data = NULL;
}
 
 
/**
* Removes a DAG head from the graph, and moves any new dag heads into the
* heads list.
*/
void
dag_prune_head(struct dag *dag, struct dag_node *node)
{
   assert(!node->parent_count);
   list_delinit(&node->link);
 
 
   util_dynarray_foreach(&node->edges, struct dag_edge, edge) {
      dag_remove_edge(dag, edge);
   }
}
 
本文主要是通過對《Engineering a compiler》翻譯整理而來。
本文中參考的程式碼若無特別指出均是來源於mesa中的源文件 src\util\dag.c 和 src\util\dag.c。
 
參考資料：
Advanced compiler design and implementation / Steve Muchnick.
Tags:

VirMach 便宜 VPS

QNews

QNews