Last active
June 19, 2024 12:43
-
-
Save matejker/6d9305e23a168ed66d3260eb261bb98b to your computer and use it in GitHub Desktop.
Revisions
-
matejker revised this gist
Nov 12, 2020 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -12,7 +12,7 @@ "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { -
Sep 21, 2020 . 1 changed file with 2 additions and 2 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -128,8 +128,8 @@ "```\n", " E := E'\n", " for all node i ∈ N do\n", " compute A(i), the set of ancestors nodes of task i\n", " compute P(i), the set of parents nodes of task i\n", " end for\n", " \n", " for all node i ∈ N do\n", -
Sep 17, 2020 . 1 changed file with 1 addition and 1 deletion.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -5,7 +5,7 @@ "metadata": {}, "source": [ "# Optimization Algorithm of Task Dependency Graph for Scheduling\n", "A simple algorithm which optimize dependency graph by removing unnecessary and duplicated dependencies. In this notebook we provide two [isomorphic?] solution. First, when dependency graph is defended downstream, meaning every node knows all nodes which depends on it (children and descendants). Second, (I think more common) when each node knows its dependencies (parents and ancestors). The original idea of children and descendants comes from Cheng’s paper [1]." ] }, { -
Sep 17, 2020 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,212 @@ { "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Optimization Algorithm of Task Dependency Graph for Scheduling\n", "A simple algorithm which optimize dependency graph by removing unnecessary and duplicated dependencies. In this notebook we provide two [isomorfic?] solution. First, when dependency graph is definded downstream, meaning every node knows all nodes which depends on it (children and descendants). Second, (I _think_ more common) when each node knows its dependecies (parents and ancestors). The original idea of children and descendants comes from Cheng's paper [1]." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "_Figures 👆 shows how we can simplify dependecy graph by removing common dependecies._\n", "\n", "**Definition:** Dependency graph is a _Directed Acyclic Graph_ (or _DAG_) where a dependecy is pointing to node." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "from typing import Dict\n", "from copy import deepcopy\n", "from itertools import product" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "dependency_graph_1 = {\n", " 'a': {'b', 'c', 'd', 'e'}, \n", " 'b': {'e'}, \n", " 'c': {'d'}, \n", " 'd': {'e'}, \n", " 'e': {}\n", "}\n", "\n", "dependency_graph_2 = {\n", " 'a': {}, \n", " 'b': {'a'}, \n", " 'c': {'a'}, \n", " 'd': {'a', 'c'}, \n", " 'e': {'a', 'd', 'b'}\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm 1 (children and descendants)\n", "**Input**: Task dependency graph $G=(N, E)$ \n", "**Input**: Task dependency graph $G'=(N, E')$ without redundant edges\n", "```\n", " E := E'\n", " for all node i ∈ N do\n", " compute D(i), the set of descendants nodes of task i\n", " compute C(i), the set of child nodes of task i\n", " end for\n", " \n", " for all node i ∈ N do\n", " for all j ∈ C(i), k ∈ D(i), and j ∈ D(k) do\n", " remove the edge (i, j )\n", " update C(i)\n", " E := E \\ (i, j)\n", " C(i) := C(i) \\ j\n", " end for\n", " end for\n", " return the optimized graph G = (N, E')\n", "```" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'a': {'b', 'c'}, 'b': {'e'}, 'c': {'d'}, 'd': {'e'}, 'e': {}}" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def optimize_dependency_graph_1(dependency_graph: Dict[str, set]) -> Dict[str, set]:\n", " descendants = deepcopy(dependency_graph)\n", " child = deepcopy(dependency_graph)\n", "\n", " for i in dependency_graph:\n", " parents_ancestors_combination = product(child[i], descendants[i])\n", " for (j, k) in parents_ancestors_combination:\n", " if len({i, j, k}) < 3:\n", " continue\n", " if j in descendants[k]:\n", " child[i] = child[i].difference({j})\n", "\n", " return child\n", "\n", "optimize_dependency_graph_1(dependency_graph_1)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithm 2 (parents and ancestors)\n", "**Input**: Task dependency graph $G=(N, E)$ \n", "**Input**: Task dependency graph $G'=(N, E')$ without redundant edges\n", "```\n", " E := E'\n", " for all node i ∈ N do\n", " compute A(i), the set of parents nodes of task i\n", " compute P(i), the set of ancestors nodes of task i\n", " end for\n", " \n", " for all node i ∈ N do\n", " for all j ∈ P(i), k ∈ A(i), and j ∈ A(k) do\n", " remove the edge (i, j )\n", " update P(i)\n", " E := E \\ (i, j)\n", " P(i) := P(i) \\ j\n", " end for\n", " end for\n", " return the optimized graph G = (N, E')\n", "```" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'a': {}, 'b': {'a'}, 'c': {'a'}, 'd': {'c'}, 'e': {'b', 'd'}}" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "def optimize_dependency_graph_2(dependency_graph: Dict[str, set]) -> Dict[str, set]:\n", " ancestors = deepcopy(dependency_graph)\n", " parents = deepcopy(dependency_graph)\n", "\n", " for i in dependency_graph:\n", " parents_ancestors_combination = product(parents[i], ancestors[i])\n", " for (j, k) in parents_ancestors_combination:\n", " if len({i, j, k}) < 3:\n", " continue\n", " if j in ancestors[k]:\n", " parents[i] = parents[i].difference({j})\n", "\n", " return parents\n", "\n", "optimize_dependency_graph_2(dependency_graph_2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## References \n", "[1] Zhuo CHENG Yasuo TAN Yuto LIM (2016), *rERA: An Optimization Algorithm of Task Dependency\n", "Graph for Scheduling*, https://dspace.jaist.ac.jp/dspace/bitstream/10119/14090/1/22878.pdf" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.9" } }, "nbformat": 4, "nbformat_minor": 4 }