\documentclass[11pt,twoside]{article}\makeatletter

\IfFileExists{xcolor.sty}%
  {\RequirePackage{xcolor}}%
  {\RequirePackage{color}}
\usepackage{colortbl}
\usepackage{wrapfig}
\usepackage{ifxetex}
\ifxetex
  \usepackage{fontspec}
  \usepackage{xunicode}
  \catcode`⃥=\active \def⃥{\textbackslash}
  \catcode`❴=\active \def❴{\{}
  \catcode`❵=\active \def❵{\}}
  \def\textJapanese{\fontspec{Noto Sans CJK JP}}
  \def\textChinese{\fontspec{Noto Sans CJK SC}}
  \def\textKorean{\fontspec{Noto Sans CJK KR}}
  \setmonofont{DejaVu Sans Mono}
  
\else
  \IfFileExists{utf8x.def}%
   {\usepackage[utf8x]{inputenc}
      \PrerenderUnicode{–}
    }%
   {\usepackage[utf8]{inputenc}}
  \usepackage[english]{babel}
  \usepackage[T1]{fontenc}
  \usepackage{float}
  \usepackage[]{ucs}
  \uc@dclc{8421}{default}{\textbackslash }
  \uc@dclc{10100}{default}{\{}
  \uc@dclc{10101}{default}{\}}
  \uc@dclc{8491}{default}{\AA{}}
  \uc@dclc{8239}{default}{\,}
  \uc@dclc{20154}{default}{ }
  \uc@dclc{10148}{default}{>}
  \def\textschwa{\rotatebox{-90}{e}}
  \def\textJapanese{}
  \def\textChinese{}
  \IfFileExists{tipa.sty}{\usepackage{tipa}}{}
\fi
\def\exampleFont{\ttfamily\small}
\DeclareTextSymbol{\textpi}{OML}{25}
\usepackage{relsize}
\RequirePackage{array}
\def\@testpach{\@chclass
 \ifnum \@lastchclass=6 \@ne \@chnum \@ne \else
  \ifnum \@lastchclass=7 5 \else
   \ifnum \@lastchclass=8 \tw@ \else
    \ifnum \@lastchclass=9 \thr@@
   \else \z@
   \ifnum \@lastchclass = 10 \else
   \edef\@nextchar{\expandafter\string\@nextchar}%
   \@chnum
   \if \@nextchar c\z@ \else
    \if \@nextchar l\@ne \else
     \if \@nextchar r\tw@ \else
   \z@ \@chclass
   \if\@nextchar |\@ne \else
    \if \@nextchar !6 \else
     \if \@nextchar @7 \else
      \if \@nextchar (8 \else
       \if \@nextchar )9 \else
  10
  \@chnum
  \if \@nextchar m\thr@@\else
   \if \@nextchar p4 \else
    \if \@nextchar b5 \else
   \z@ \@chclass \z@ \@preamerr \z@ \fi \fi \fi \fi
   \fi \fi  \fi  \fi  \fi  \fi  \fi \fi \fi \fi \fi \fi}
\gdef\arraybackslash{\let\\=\@arraycr}
\def\@textsubscript#1{{\m@th\ensuremath{_{\mbox{\fontsize\sf@size\z@#1}}}}}
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\def\abbr{}
\def\corr{}
\def\expan{}
\def\gap{}
\def\orig{}
\def\reg{}
\def\ref{}
\def\sic{}
\def\persName{}\def\name{}
\def\placeName{}
\def\orgName{}
\def\textcal#1{{\fontspec{Lucida Calligraphy}#1}}
\def\textgothic#1{{\fontspec{Lucida Blackletter}#1}}
\def\textlarge#1{{\large #1}}
\def\textoverbar#1{\ensuremath{\overline{#1}}}
\def\textquoted#1{‘#1’}
\def\textsmall#1{{\small #1}}
\def\textsubscript#1{\@textsubscript{\selectfont#1}}
\def\textxi{\ensuremath{\xi}}
\def\titlem{\itshape}
\newenvironment{biblfree}{}{\ifvmode\par\fi }
\newenvironment{bibl}{}{}
\newenvironment{byline}{\vskip6pt\itshape\fontsize{16pt}{18pt}\selectfont}{\par }
\newenvironment{citbibl}{}{\ifvmode\par\fi }
\newenvironment{docAuthor}{\ifvmode\vskip4pt\fontsize{16pt}{18pt}\selectfont\fi\itshape}{\ifvmode\par\fi }
\newenvironment{docDate}{}{\ifvmode\par\fi }
\newenvironment{docImprint}{\vskip 6pt}{\ifvmode\par\fi }
\newenvironment{docTitle}{\vskip6pt\bfseries\fontsize{22pt}{25pt}\selectfont}{\par }
\newenvironment{msHead}{\vskip 6pt}{\par}
\newenvironment{msItem}{\vskip 6pt}{\par}
\newenvironment{rubric}{}{}
\newenvironment{titlePart}{}{\par }

\newcolumntype{L}[1]{){\raggedright\arraybackslash}p{#1}}
\newcolumntype{C}[1]{){\centering\arraybackslash}p{#1}}
\newcolumntype{R}[1]{){\raggedleft\arraybackslash}p{#1}}
\newcolumntype{P}[1]{){\arraybackslash}p{#1}}
\newcolumntype{B}[1]{){\arraybackslash}b{#1}}
\newcolumntype{M}[1]{){\arraybackslash}m{#1}}
\definecolor{label}{gray}{0.75}
\def\unusedattribute#1{\sout{\textcolor{label}{#1}}}
\DeclareRobustCommand*{\xref}{\hyper@normalise\xref@}
\def\xref@#1#2{\hyper@linkurl{#2}{#1}}
\begingroup
\catcode`\_=\active
\gdef_#1{\ensuremath{\sb{\mathrm{#1}}}}
\endgroup
\mathcode`\_=\string"8000
\catcode`\_=12\relax

\usepackage[a4paper,twoside,lmargin=1in,rmargin=1in,tmargin=1in,bmargin=1in,marginparwidth=0.75in]{geometry}
\usepackage{framed}

\definecolor{shadecolor}{gray}{0.95}
\usepackage{longtable}
\usepackage[normalem]{ulem}
\usepackage{fancyvrb}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage{marginnote}

\renewcommand{\@cite}[1]{#1}


\renewcommand*{\marginfont}{\itshape\footnotesize}

\def\Gin@extensions{.pdf,.png,.jpg,.mps,.tif}

  \pagestyle{fancy}

\usepackage[pdftitle={Performance Comparison of BNP Scheduling Algorithms in Homogeneous Environment},
 pdfauthor={}]{hyperref}
\hyperbaseurl{}

	 \paperwidth210mm
	 \paperheight297mm
              
\def\@pnumwidth{1.55em}
\def\@tocrmarg {2.55em}
\def\@dotsep{4.5}
\setcounter{tocdepth}{3}
\clubpenalty=8000
\emergencystretch 3em
\hbadness=4000
\hyphenpenalty=400
\pretolerance=750
\tolerance=2000
\vbadness=4000
\widowpenalty=10000

\renewcommand\section{\@startsection {section}{1}{\z@}%
     {-1.75ex \@plus -0.5ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large\bfseries}}
\renewcommand\subsection{\@startsection{subsection}{2}{\z@}%
     {-1.75ex\@plus -0.5ex \@minus- .2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\Large}}
\renewcommand\subsubsection{\@startsection{subsubsection}{3}{\z@}%
     {-1.5ex\@plus -0.35ex \@minus -.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\large}}
\renewcommand\paragraph{\@startsection{paragraph}{4}{\z@}%
     {-1ex \@plus-0.35ex \@minus -0.2ex}%
     {0.5ex \@plus .2ex}%
     {\reset@font\normalsize}}
\renewcommand\subparagraph{\@startsection{subparagraph}{5}{\parindent}%
     {1.5ex \@plus1ex \@minus .2ex}%
     {-1em}%
     {\reset@font\normalsize\bfseries}}


\def\l@section#1#2{\addpenalty{\@secpenalty} \addvspace{1.0em plus 1pt}
 \@tempdima 1.5em \begingroup
 \parindent \z@ \rightskip \@pnumwidth 
 \parfillskip -\@pnumwidth 
 \bfseries \leavevmode #1\hfil \hbox to\@pnumwidth{\hss #2}\par
 \endgroup}
\def\l@subsection{\@dottedtocline{2}{1.5em}{2.3em}}
\def\l@subsubsection{\@dottedtocline{3}{3.8em}{3.2em}}
\def\l@paragraph{\@dottedtocline{4}{7.0em}{4.1em}}
\def\l@subparagraph{\@dottedtocline{5}{10em}{5em}}
\@ifundefined{c@section}{\newcounter{section}}{}
\@ifundefined{c@chapter}{\newcounter{chapter}}{}
\newif\if@mainmatter 
\@mainmattertrue
\def\chaptername{Chapter}
\def\frontmatter{%
  \pagenumbering{roman}
  \def\thechapter{\@roman\c@chapter}
  \def\theHchapter{\roman{chapter}}
  \def\thesection{\@roman\c@section}
  \def\theHsection{\roman{section}}
  \def\@chapapp{}%
}
\def\mainmatter{%
  \cleardoublepage
  \def\thechapter{\@arabic\c@chapter}
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \pagenumbering{arabic}
  \setcounter{secnumdepth}{6}
  \def\@chapapp{\chaptername}%
  \def\theHchapter{\arabic{chapter}}
  \def\thesection{\@arabic\c@section}
  \def\theHsection{\arabic{section}}
}
\def\backmatter{%
  \cleardoublepage
  \setcounter{chapter}{0}
  \setcounter{section}{0}
  \setcounter{secnumdepth}{2}
  \def\@chapapp{\appendixname}%
  \def\thechapter{\@Alph\c@chapter}
  \def\theHchapter{\Alph{chapter}}
  \appendix
}
\newenvironment{bibitemlist}[1]{%
   \list{\@biblabel{\@arabic\c@enumiv}}%
       {\settowidth\labelwidth{\@biblabel{#1}}%
        \leftmargin\labelwidth
        \advance\leftmargin\labelsep
        \@openbib@code
        \usecounter{enumiv}%
        \let\p@enumiv\@empty
        \renewcommand\theenumiv{\@arabic\c@enumiv}%
	}%
  \sloppy
  \clubpenalty4000
  \@clubpenalty \clubpenalty
  \widowpenalty4000%
  \sfcode`\.\@m}%
  {\def\@noitemerr
    {\@latex@warning{Empty `bibitemlist' environment}}%
    \endlist}

\def\tableofcontents{\section*{\contentsname}\@starttoc{toc}}
\parskip0pt
\parindent1em
\def\Panel#1#2#3#4{\multicolumn{#3}{){\columncolor{#2}}#4}{#1}}
\newenvironment{reflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemsep}{0pt}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\itshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{sansreflist}{%
  \begin{raggedright}\begin{list}{}
  {%
   \setlength{\topsep}{0pt}%
   \setlength{\rightmargin}{0.25in}%
   \setlength{\itemindent}{0pt}%
   \setlength{\parskip}{0pt}%
   \setlength{\itemsep}{0pt}%
   \setlength{\parsep}{2pt}%
   \def\makelabel##1{\upshape ##1}}%
  }
  {\end{list}\end{raggedright}}
\newenvironment{specHead}[2]%
 {\vspace{20pt}\hrule\vspace{10pt}%
  \phantomsection\label{#1}\markright{#2}%

  \pdfbookmark[2]{#2}{#1}%
  \hspace{-0.75in}{\bfseries\fontsize{16pt}{18pt}\selectfont#2}%
  }{}
      \def\TheFullDate{2012-05-15 (revised: 15 May 2012)}
\def\TheID{\makeatother }
\def\TheDate{2012-05-15}
\title{Performance Comparison of BNP Scheduling Algorithms in Homogeneous Environment}
\author{}\makeatletter 
\makeatletter
\newcommand*{\cleartoleftpage}{%
  \clearpage
    \if@twoside
    \ifodd\c@page
      \hbox{}\newpage
      \if@twocolumn
        \hbox{}\newpage
      \fi
    \fi
  \fi
}
\makeatother
\makeatletter
\thispagestyle{empty}
\markright{\@title}\markboth{\@title}{\@author}
\renewcommand\small{\@setfontsize\small{9pt}{11pt}\abovedisplayskip 8.5\p@ plus3\p@ minus4\p@
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus2\p@
\belowdisplayshortskip 4\p@ plus2\p@ minus2\p@
\def\@listi{\leftmargin\leftmargini
               \topsep 2\p@ plus1\p@ minus1\p@
               \parsep 2\p@ plus\p@ minus\p@
               \itemsep 1pt}
}
\makeatother
\fvset{frame=single,numberblanklines=false,xleftmargin=5mm,xrightmargin=5mm}
\fancyhf{} 
\setlength{\headheight}{14pt}
\fancyhead[LE]{\bfseries\leftmark} 
\fancyhead[RO]{\bfseries\rightmark} 
\fancyfoot[RO]{}
\fancyfoot[CO]{\thepage}
\fancyfoot[LO]{\TheID}
\fancyfoot[LE]{}
\fancyfoot[CE]{\thepage}
\fancyfoot[RE]{\TheID}
\hypersetup{citebordercolor=0.75 0.75 0.75,linkbordercolor=0.75 0.75 0.75,urlbordercolor=0.75 0.75 0.75,bookmarksnumbered=true}
\fancypagestyle{plain}{\fancyhead{}\renewcommand{\headrulewidth}{0pt}}

\date{}
\usepackage{authblk}

\providecommand{\keywords}[1]
{
\footnotesize
  \textbf{\textit{Index terms---}} #1
}

\usepackage{graphicx,xcolor}
\definecolor{GJBlue}{HTML}{273B81}
\definecolor{GJLightBlue}{HTML}{0A9DD9}
\definecolor{GJMediumGrey}{HTML}{6D6E70}
\definecolor{GJLightGrey}{HTML}{929497} 

\renewenvironment{abstract}{%
   \setlength{\parindent}{0pt}\raggedright
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
   \textcolor{GJBlue}{\large\bfseries\abstractname\space}
}{%   
   \vskip8pt
   \textcolor{GJMediumGrey}{\rule{\textwidth}{2pt}}
   \vskip16pt
}

\usepackage[absolute,overlay]{textpos}

\makeatother 
      \usepackage{lineno}
      \linenumbers
      
\begin{document}

             \author[1]{Dr. Nidhi  Arora}

             \affil[1]{  Maharishi Markandeshwar University}

\renewcommand\Authands{ and }

\date{\small \em Received: 6 April 2012 Accepted: 30 April 2012 Published: 15 May 2012}

\maketitle


\begin{abstract}
        


Static Scheduling is the mapping of a program to the resources of a parallel system in order to minimize the execution time. This paper presents static scheduling algorithms that schedule an edge-weighted directed acyclic graph (DAG) to a set of homogeneous processors. The aim is to evaluate and compare the performance of different algorithms and select the best algorithm amongst them. Various BNP algorithms are analyzed and classified into four groups - Highest Level First Estimated Time (HLFET), Dynamic Level Scheduling (DLS), Modified Critical Path (MCP) and Earliest Time First (ETF). Based upon their performance considering various factors, best algorithm is determined.

\end{abstract}


\keywords{DAG, Task graphs, Parallel Processing, List Scheduling, Multiprocessor, Speed up.}

\begin{textblock*}{18cm}(1cm,1cm) % {block width} (coords) 
\textcolor{GJBlue}{\LARGE Global Journals \LaTeX\ JournalKaleidoscope\texttrademark}
\end{textblock*}

\begin{textblock*}{18cm}(1.4cm,1.5cm) % {block width} (coords) 
\textcolor{GJBlue}{\footnotesize \\ Artificial Intelligence formulated this projection for compatibility purposes from the original article published at Global Journals. However, this technology is currently in beta. \emph{Therefore, kindly ignore odd layouts, missed formulae, text, tables, or figures.}}
\end{textblock*}


\let\tabcellsep& 	 	 		 
\section[{Introduction}]{Introduction}\par
arallel processing is the simultaneous use of more than one processor to execute a program in order to get faster results. Given an directed acyclic graph (DAG), also called task graph, in which the nodes represent the tasks and edges represent the communication costs as well as the dependencies among the tasks. The problem deals with the scheduling of the tasks onto a set of homogenous processors to minimize the completion time. DAG is generic model of a parallel program consisting of a set of processes. Each process is an indivisible unit of execution, expressed by node. A node has one or more inputs and can have one or more output to various nodes.\par
The paper is organized as follows. In the next section, we describe the generic DAG model and its suitability to different situations. In section 3, basic scheduling attributes are being discussed. Classification of BNP scheduling algorithms is given in section 4. Section 5, presents a performance comparison of various BNP scheduling algorithms and results are derived. Last section concludes the paper and presents the scope of this work in future. 
\section[{II. Dag model}]{II. Dag model}\par
The DAG \hyperref[b0]{[Kaur et al, 2011}][Ahmad and  {\ref Kwok,1998}] is generic model of a parallel program consisting of a set of processes among which there are dependencies. Each process is an indivisible unit of execution, expressed by node. A node has one or more inputs and can have one or more output to various nodes. When all inputs are available, the node is triggered to execute. After its execution, it generates its output. In this model, a set of nodes \{ n 1 , n 2 , n 3 ???. n n \} are connected by a set of directed edges, which are represented by (n i , n j ) where n i is called the Parent node and n j is called the child node. A node without parent is called an Entry node and a node without child called an Exit node. The weight of a node, denoted by w (n i ), represents the process execution time of a process. Since each edge corresponds to a message transfer from one process to another, the communication time, denoted by c (n i , n j ) is equal to the message transmission time from node n i to n j . Thus c (n i , n j ) becomes zero when and are scheduled to the same processor because intraprocessor communication time is negligible compared with the interprocessor communication time. The node and edge weights are usually obtained by estimations. Some variations in the generic DAG model are described below:\par
Accurate Model \hyperref[b0]{[Kaur et al, 2011]}: In an accurate model, the weight of a node includes the computation time, the time to receive messages before the computation, and the time to send messages after the computation. The weight of an edge is a function of the distance between the source and destination nodes, and therefore, depends on the node allocation and network topology. It also depends on network contention which can be difficult to model. When two nodes are assigned to a single processor, the edge weight becomes zero, so as the message receiving time and sending time.\par
Approximate Model 1 \hyperref[b0]{[Kaur et al, 2011}]: In this model, the edge weight is approximated by a constant, independent of the message transmission distance and network contention. A completely connected network without contention fits this model.\par
Approximate Model 2 \hyperref[b0]{[Kaur et al, 2011}]: In this model, the message receiving time and sending time are ignored in addition to approximating the edge weight by a constant. These approximate models are best suited to the following situations; (i) the grain-size of the process is much larger than the message April n j n i receiving time and sending time; (ii) communication is handled by some dedicated hardware so that the processor spends insignificant amount of time on communication; (iii) the message transmission time varies little with the message transmission distance, e.g., in a wormhole or circuit switching network; and (iv) the network is not heavily loaded. In general, the approximate models can be used for medium to large granularity, since the larger the process grain-size, the less the communication, and consequently the network is not heavily loaded. The second reason for using the approximate models is that both the node and edge weights are obtained by estimation, which is hardly accurate. Thus, an accurate model is useless when the weights of nodes and edges are not accurate. 
\section[{III. List scheduling}]{III. List scheduling}\par
Most scheduling algorithms are based on list scheduling technique \hyperref[b10]{[Kwok and Ahmad, 1999]}. List scheduling is a class of scheduling heuristics in which the nodes are assigned priorities and placed in a list arranged in a descending order of priority. The node with higher priority will be examined for scheduling before a node with a lower priority. If more than one node has the same priority, ties are broken using some method. List scheduling consists of two phases: 1. Task prioritizing phase: -In this phase the priority of each node in DAG is computed and assigned. 2. Processor selection:-Each task is assigned processor with minimum execution time.\par
The two main attributes  {\ref [Hagras and Janeek, 2003]} for assigning priority are the t-level (top level) and b-level (bottom level).\par
Top level : The t-level of a node n i is the length of the longest path from an entry node to n i (excluding n i ). Here, the length of a path is the sum of all the node and edge weights along the path. The t-level is computed recursively by traversing the DAG downward starting from the entry node n entry . 
\section[{t-level (n}]{t-level (n}i ) = max (t-level (n m ) + w m + c m , i )\par
where n m is predecessors of n i , w m stands for computational cost, c m , i stands for communication cost and t-level (n entry ) = 0. The t-level of n i highly correlates with n i 's earliest start time, denoted by EST (n i ) , which is determined after n i is scheduled to a processor.\par
Bottom level: The b-level of a node n i is the length of the longest path from node n i to an exit node.\par
The b-level is computed recursively by traversing the DAG upward starting from the exit node n exit . 
\section[{b-level (n}]{b-level (n}i ) = w i + max(b-level (n m ) + c m , i )\par
where n m is successor of n i , w m stands for computational cost, c m , i stands for communication cost and b-level (n exit ) = w (n exit ).\par
The b-level of a node is bounded by the length of the critical path. A critical path (CP) of a DAG, is the longest path from an entry node to an exit node.\par
Static b-level: Some BNP scheduling algorithms do not consider the edge weights in computing the blevel. In that case, b-level does not change throughout the scheduling process, therefore it is called static blevel or static level (SL). SL(n i ) = w i + max (SL(n m ) )\par
where n m is successor of n i and SL(n exit ) = w (n exit ) ALAP start time: The ALAP (As-Late-As-Possible) start time of a node is measure of how far the node's start time can be delayed without increasing the schedule length. It is also known as latest start time (LST).\par
LST(n i ) = min(LST(n m ) -c m , i ) -w i where is successor of n i , w m stands for computational cost, c m , i stands for communication cost and LST(n exit ) = EST(n exit ).\par
Dynamic Level: It is the difference of Static level and Earliest Start Time.\par
Some algorithms assign higher priority to a node with smaller t-level while some algorithms assign higher priority to a node with larger b-level. A priority table is designed for all the nodes in DAG. 
\section[{IV.}]{IV.} 
\section[{Classification of bnp scheduling algorithms}]{Classification of bnp scheduling algorithms}\par
BNP refers to Bounded Number of Processor (BNP) Scheduling Algorithms  {\ref [Hagras and Janeek, 2003}] \hyperref[b0]{[Kaur et al, 2011]}. These algorithms schedule the DAG to a bounded number of processors directly. The processors are assumed to be fully connected. BNP scheduling algorithms are based on the list scheduling technique in which nodes are assigned some priorities. To study these algorithms, homogeneous environment is considered in which processors having same configuration are used for execution. BNP class of algorithms is categorized into two categories:\par
Static Algorithms: These algorithms use list scheduling approach. Therefore in static algorithms once the task prioritization phase is finished then and only then the processor selection phase begins. Following are static scheduling algorithms.\par
Highest Level First with Estimated Times (HLFET) algorithm \hyperref[b10]{[Kwok and Ahmad, 1999}]: It is one of the simplest list scheduling algorithms that uses static b-level as node priority and ignores the communication costs on the edges. Following steps describe the HLFET algorithm in detail: 1. Calculate the static b-level of each node. 2. Make a ready list in descending order of static blevel. The ready list contains only the entry nodes initially. Ties are broken randomly.\par
Repeat.\par
3. Schedule the first node in the ready list to a processor that allows the earliest execution, using the non-insertion approach. 4. Update the ready list by inserting the nodes that are now ready. Until all nodes are scheduled.\par
Modified Critical Path (MCP) algorithm \hyperref[b10]{[Kwok and Ahmad, 1999]}: This algorithm uses an attribute called ALAP time of a node as a priority. The ALAP time of a node is computed by first computing the length of CP and then subtracting the b-level of the node from it. Therefore, the ALAP times of the nodes on the CP are just their t-levels. Following steps describe the algorithm. 1. Compute the ALAP time of each node. 2. For each node, create a list which consists of the ALAP times of the node itself and all its children in a descending order. 3. Sort these lists in an ascending order. Create a node list according to this order. Repeat. 4. Schedule the first node in the node list to a processor that allows the earliest execution, using the insertion approach. 5. Remove the node from the node list. Until the node list is empty.\par
Dynamic Algorithms: These algorithms also use list scheduling approach. In Dynamic algorithms both the task prioritization phase and processor selection phase goes on side by side. Following are dynamic scheduling algorithms.\par
The Earliest Time First (ETF) algorithm  {\ref [Kwok and Ahmad,1999]}: It computes, at each step, the earliest start times for all ready nodes and then selects the one with the smallest start time, which is computed by examining the start time of the node on all processors exhaustively. The algorithm is described below. 1. Compute the static b-level of each node. 2. Initially, the pool of ready nodes include only the entry nodes. Repeat. 
\section[{Calculate the earliest start time on each processor}]{Calculate the earliest start time on each processor}\par
for each node in the ready pool. Pick the nodeprocessor pair that gives the earliest time using the non insertion approach. Ties are broken by selecting the node with a higher static b-level. Schedule the node to the corresponding processor. 4. Add the newly ready nodes to the ready node pool. Until all nodes are scheduled. Dynamic Level Scheduling (DLS) algorithm \hyperref[b10]{[Kwok and Ahmad, 1999}]: This algorithm uses as node priority an attribute called dynamic level (DL) which is the difference between the static b-level of a node and its earliest start time on a processor. The stepwise description of the algorithm is given below. 1. Calculate the b-level of each node. 2. Initially, the ready node pool includes only the entry nodes. Repeat. 3. Calculate the earliest start time for every node on each processor. Hence, compute the DL of every node processor pair by subtracting the earliest start time from the node's static b-level. 4. Select the node processor pair that gives the largest DL. Schedule the node to the corresponding processor. 5. Add the newly ready nodes to the ready pool. Until all nodes are scheduled.\par
V. 
\section[{Performance comparison and results}]{Performance comparison and results}\par
The performance is the most important factor in every algorithm  {\ref [Kaur et al, 2011] [Hagras and} {\ref Janeek, 2003]}. In this section, we present performance comparison of above discussed BNP scheduling algorithm. The performance comparison is based upon various comparison metrics discussed below.\par
Makespan: Makespan is defined as the completion time of the algorithm. It is calculated by measuring the finishing time of the exit task by the algorithm.\par
Speed Up: The Speed Up value is computed by dividing the sequential execution time by the parallel execution time.\par
Scheduled length ratio (SLR): It is defined as the ratio of the Makespan of the algorithm to Critical path values of the DAG.\par
Processor Utilization: It means that how processors are being utilized by different processes. It is good when maximum number processors are utilized.\par
Above metrices are compared for 10 nodes, 15 nodes, 20 nodes and 25 nodes in homogeneous environment and results are shown graphically.\par
Case 1 : In first case, results are shown for 10 nodes and 5 processors. Makespan and SLR is same for HLFET, MCP and ETF, but DLS algorithm shows highest makespan value and lowest speed up value. All processors are best utilized in case of HLFET and MCP.      
\section[{VI. Conclusion and future scope}]{VI. Conclusion and future scope}\par
Makespan of MCP and ETF showed large increase in value while increasing the tasks from 20 to 25 compared to other algorithms. The average processor utilization remained same for HLFET and MCP algorithms with 10 tasks. MCP utilized processor efficiently than HLFET with 15 tasks. With 20 and 25 tasks, HLFET proved to be better than other algorithms. The SLR remained almost the same for HLFET, MCP and ETF with 10 tasks. It is maximum in case of DLS for 10 tasks. With 15 tasks MCP shows the lowest value. As the tasks are increased HLFET shows the lesser value in case of 20 and 25 tasks. Same is the case with Speed Up. With 10 tasks speedup of HLFET, MCP and DLS algorithms is same. As the tasks increase from 20 to 25, Speed Up value of HLFET hikes. It can be concluded from the above results, that HLFET is one of the efficient algorithms, considering the data gathered using the scenarios and the performance calculated from them. The thesis has vast future scope. A lot of work can be done considering more case scenarios. Heterogeneous environment can be considered, in which multiple processors having different configuration are used. The comparison of these algorithms can be done for any\begin{figure}[htbp]
\noindent\textbf{1}\includegraphics[]{image-2.png}
\caption{\label{fig_0}Figure 1 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{2345}\includegraphics[]{image-3.png}
\caption{\label{fig_1}Figure 2 :Figure 3 : 4 :Figure 5 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{7}\includegraphics[]{image-4.png}
\caption{\label{fig_2}Figure 7 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{911}\includegraphics[]{image-5.png}
\caption{\label{fig_3}Figure 9 :Figure 11 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{12}\includegraphics[]{image-6.png}
\caption{\label{fig_4}Figure 12 :}\end{figure}
 			\footnote{© 2012 Global Journals Inc. (US) Global Journal of Computer Science and Technology Volume XII Issue VIII Version I} 			\footnote{© 2012 Global Journals Inc. (US)} 		 		\backmatter  			  				\begin{bibitemlist}{1}
\bibitem[Liou and Palis (1997)]{b14}\label{b14} 	 		‘A Comparison of General Approaches to Multiprocessor Scheduling’.  		 			Jing-Chiou Liou 		,  		 			Micheal A Palis 		.  	 	 		\textit{IEEE}  		15 April 1997. p. .  	 
\bibitem[Adam et al.]{b9}\label{b9} 	 		\textit{A Comparison of List scheduling for Parallel},  		 			T Adam 		,  		 			K Chandy 		,  		 			J Dickson 		.  		 	 
\bibitem[Jin et al. (2008)]{b7}\label{b7} 	 		\textit{A performance study of multiprocessor task scheduling algorithm},  		 			Shyiyuan Jin 		,  		 			Guy Schiavone 		,  		 			Damla Turgut 		.  		Jan -2008. 43 p. .  	 
\bibitem[Casavant (1988)]{b8}\label{b8} 	 		‘A taxonomy of Scheduling in General-Purpose Distributed Computing Systems’.  		 			Thomas L Casavant 		.  	 	 		\textit{IEEE Transactions on Software Engineering}  		February 1988. 14  (2) .  	 
\bibitem[Sudha and Tjanushkodi ()]{b13}\label{b13} 	 		‘An Approach for parallel job Scheduling Using supple Algorithm’.  		 			S Sudha 		,  		 			K Tjanushkodi 		.  		 \url{download/repository/Grudenickvalifikacijski.pdf14}  	 	 		\textit{Asian Journal of Information Technology}  		2008.  (7)  p. .  	 
\bibitem[Kaur et al. (2011)]{b0}\label{b0} 	 		‘Analysis, Comparison and Performance Evaluation of BNP Scheduling Algorithms in Parallel Processing’.  		 			Parneet Kaur 		,  		 			Dheerendra Singh 		,  		 			Gurvinder Singh 		,  		 			Navneet Singh 		.  	 	 		\textit{International Journal of Information Technology and Knowledge Management}  		January-June 2011. 4  (1)  p. .  	 
\bibitem[Ahmad and Wu ()]{b3}\label{b3} 	 		\textit{Analysis, Evaluation and Comparison Of algorithm for Scheduling Task Graph on Parallel Processor},  		 			Ishfaq Ahmad 		,  		 			Min-You Wu 		.  		1996. IEEE. p. .  	 
\bibitem[Ahmad and Kwok ()]{b2}\label{b2} 	 		\textit{Benchmarking and comparison of the Task Graph Scheduling algorithms},  		 			Ishfaq Ahmad 		,  		 			Yu-Kwong Kwok 		.  		1998. IEEE. p. .  	 
\bibitem[Laskowski]{b11}\label{b11} 	 		\textit{Fast Scheduling and Partitioning algorithm in the multiprocessor system with Redundant Communication Resources},  		 			Eryk Laskowski 		.  		 \url{www.springerlink.com/content/0np00wu1r0c7te8m/fulltext.pdf}  		 	 
\bibitem[Wu (1997)]{b6}\label{b6} 	 		‘On parallelization of Static Scheduling Algorithm’.  		 			Min You Wu 		.  	 	 		\textit{IEEE}  		Aug 1997. 23 p. .  	 
\bibitem[Dror et al.]{b5}\label{b5} 	 		\textit{Parallel Job Scheduling: Issues and Approaches},  		 			G Dror 		,  		 			Larry Feitelson 		,  		 			Rudolph 		.  		 \url{www.cse.Hcmut.edu.vn/\textasciitilde ptvu/ppds/ParallelJobScheduling.pdf}  		 	 
\bibitem[Ahmad and Kwok]{b1}\label{b1} 	 		\textit{Performance Comparison of Algorithm for Static Scheduling of DAG to multiprocessor" citeseerx},  		 			Ishfaq Ahmad 		,  		 			Yu-Kwong Kwok 		.  		 	 	 (ist.psu.edu/view doc/download?doi=10.1.1.42.8979...pdf) 
\bibitem[Grudenic]{b12}\label{b12} 	 		\textit{Scheduling Algorithm and Support Tools for parallel System},  		 			Igor Grudenic 		.  		 \url{www.fer.hr/\textunderscore }  		 	 
\bibitem[Kwok and Ahmad (1999)]{b10}\label{b10} 	 		‘Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors’.  		 			Yu-Kwong Kwok 		,  		 			Isfaq Ahmad 		.  	 	 		\textit{ACM Computing Surveys}  		December 1999. 31  (4) .  	 
\bibitem[Hagras and Janeek ()]{b4}\label{b4} 	 		‘Static Vs. Dynamic Listscheduling Performance Comparison’.  		 			T Hagras 		,  		 			J Janeek 		.  	 	 		\textit{Acta Polytechnica}  		2003. 43  (6) .  	 
\end{bibitemlist}
 			 		 	 
\end{document}
