summeryang98/peft

Implementation of PEFT (Predict Earliest Finish Time) DAG Scheduling Algorithm in Python

PEFT: Predict Earliest Finish Time

A Python 3.6+ implementation of a heuristic DAG scheduling approach from

H. Arabnejad and J. G. Barbosa, "List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table," in IEEE Transactions on Parallel and Distributed Systems, vol. 25, no. 3, pp. 682-694, March 2014. doi: 10.1109/TPDS.2013.57

IEEE Explore Link

Installation

Setting up a virtual environment first is recommended

After that, all necessary dependencies can be installed with pip install -r requirements.txt

Otherwise, the main dependencies are:

• Python 3.6+ (uses literal string interpolation)
• Matplotlib
• Numpy
• Networkx
• Pytest (development dependency only)
• nb_conda (only if using a conda environment & want jupyter notebook to use the right python version)

Finally, if you want it available as a local package for availability elsewhere on your system, it can be installed with pip install .

Command line Usage

Basic usage is given by python -m peft.peft -h

usage: peft.py [-h] [-d DAG_FILE] [-p PE_CONNECTIVITY_FILE]
               [-t TASK_EXECUTION_FILE]
               [-l {DEBUG,INFO,WARNING,ERROR,CRITICAL}] [--showDAG]
               [--showGantt]

A tool for finding PEFT schedules for given DAG task graphs

optional arguments:
  -h, --help            show this help message and exit
  -d DAG_FILE, --dag_file DAG_FILE
                        File containing input DAG to be scheduled. Uses
                        default 10 node dag from Arabnejad 2014 if none given.
  -p PE_CONNECTIVITY_FILE, --pe_connectivity_file PE_CONNECTIVITY_FILE
                        File containing connectivity/bandwidth information
                        about PEs. Uses a default 3x3 matrix from Arabnejad
                        2014 if none given.
  -t TASK_EXECUTION_FILE, --task_execution_file TASK_EXECUTION_FILE
                        File containing execution times of each task on each
                        particular PE. Uses a default 10x3 matrix from
                        Arabnejad 2014 if none given.
  -l {DEBUG,INFO,WARNING,ERROR,CRITICAL}, --loglevel {DEBUG,INFO,WARNING,ERROR,CRITICAL}
                        The log level to be used in this module. Default: INFO
  --showDAG             Switch used to enable display of the incoming task DAG
  --showGantt           Switch used to enable display of the final scheduled
                        Gantt chart

If you don't have any particular DAG that needs scheduling, the canonical example schedule from Topcuoglu et al. can be generated by passing in no args

python -m peft.peft

With a generated Gantt chart available using

python -m peft.peft --showGantt

Testing

If Pytest is installed, tests can be executed simply by running pytest from the repository root directory