\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={Analytical Performance Comparison of BNP Scheduling Algorithms},
 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-01-15 (revised: 15 January 2012)}
\def\TheID{\makeatother }
\def\TheDate{2012-01-15}
\title{Analytical Performance Comparison of BNP Scheduling Algorithms}
\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]{Gagandeep  Kaur}

             \author[2]{Er. Navneet  Singh}

             \author[3]{Parneet  Kaur}

             \affil[1]{  }

\renewcommand\Authands{ and }

\date{\small \em Received: 9 December 2011 Accepted: 1 January 2012 Published: 15 January 2012}

\maketitle


\begin{abstract}
        


Parallel computing is related to the application of many computers running in parallel to solve computationally intensive problems. One of the biggest issues in parallel computing is efficient task scheduling. In this paper, we survey the algorithms that allocate a parallel program represented by an edge-directed acyclic graph (DAG) to a set of homogenous processors with the objective of minimizing the completion time. We examine several such classes of algorithms and then compare the performance of a class of scheduling algorithms known as the bounded number of processors (BNP) scheduling algorithms. Comparison is based on various scheduling parameters such as makespan, speed up, processor utilization and scheduled length ratio. The main focus is given on measuring the impact of increasing the number of tasks and processors on the performance of these four BNP scheduling algorithms.

\end{abstract}


\keywords{Parallel computing, Scheduling, DAG, Homogeneous processors.}

\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 computing is a technique of executing multiple tasks simultaneously on multiple processors. The main goal of parallel computing is to increase the speed of computation. Efficient task scheduling \& mapping is one of the biggest issue in homogeneous parallel computing environment \hyperref[b0]{[1]}. The objective of Scheduling is to manage the execution of tasks in such a way that certain optimality criterion is met. Most scheduling algorithms are based on listscheduling technique \hyperref[b3]{[4]} \hyperref[b5]{[6]}[2] \hyperref[b11]{[11]}. There are two phases in List-scheduling technique: task prioritizing phase, where the priority is computed and assigned to each node in DAG, and a processor selection phase, where each task in is assigned to a processor in order of the priority of nodes that minimizes a suitable cost function. List scheduling algorithms are classified as static list scheduling if the processor selection phase starts after completion of the task prioritizing phase and dynamic list scheduling algorithm if the two phases are interleaved. A parallel program can be represented by a node-and edge-weighted directed acyclic graph (DAG) \hyperref[b1]{[2]} \hyperref[b2]{[3]}. The Directed Acyclic Graph is a generic model of a parallel program consisting of a set of processes. The nodes represent the application process and the edges represent the data dependencies among these processes.\par
This paper surveys various scheduling algorithms that schedule an edge-weighted directed acyclic graph (DAG), which is also called a task graph, to a set of homogeneous processors. We examine four classes of algorithms: Bounded Number of Processors (BNP) scheduling algorithms, Unlimited Number of Clusters (UNC) scheduling algorithms, and Arbitrary Processor Network (APN) \& Task Duplication Based (TDB) scheduling algorithms. Performance comparisons are made for the BNP algorithms. We provide qualitative analyses by measuring the performance of these four BNP scheduling algorithms under useful scheduling parameters: makespan, speed up, processor utilization, and scheduled length ratio.\par
The rest of this paper is organized as follows. In the next section, we describe the generic DAG model and discuss its variations \& techniques. A classification of scheduling algorithms is presented in Section 3.The four BNP scheduling algorithms are discussed in Section 4.The performance results and comparisons are presented in Section 5, Section 6 concludes the paper. Section 7 suggest about future scope of research. 
\section[{II.}]{II.} 
\section[{Task scheduling problem \& model used}]{Task scheduling problem \& model used}\par
This section presents the application model used for task scheduling. The number of processors could be limited or unlimited. The homogeneous computing environment model is used for the surveyed algorithms. We first introduce the directed acyclic graph (DAG) model of a parallel program. This is followed by a discussion about some basic techniques used in most scheduling algorithms \& homogeneous computing environment. 
\section[{a) The DAG Model}]{a) The DAG Model}\par
The Directed Acyclic Graph \hyperref[b1]{[2]}[3] is a generic model of a parallel program consisting of a set of processes among which there are dependencies. The DAG model that we use within this analysis is presented below in Fig. \hyperref[fig_0]{1} A task without any parent is called an entry task and a task without any child is called an exit task. A node cannot start execution before it gathers all of the messages from its parent nodes. The communication cost between two tasks assigned to the same processor is assumed to be zero. If node ni is scheduled to some processor, then ST(ni ) and FT(ni)denote the start-time and finish-time of ni, respectively.After all the nodes have been scheduled, the schedule length is defined as maxi\{FT(ni)\}across all processors. The node-and edge-weights are usually obtained by estimation. Some variations in the generic DAG model are:-Accurate model \hyperref[b1]{[2]}[3]-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 the destination nodes. It also depends on network topology and contention which can be difficult to model. When two nodes are assigned to a single processor, the edge weight becomes zero. Approximate model 1 \hyperref[b1]{[2]}[3] -Here the edge weight is approximated by a constant. A completely connected network without contention fits this model. Approximate model 2 \hyperref[b1]{[2]}[3]-In this model, the message receiving time and sending time are ignored in addition to approximating the edge weight by a constant.\par
An accurate model is useless when the weights of nodes and edges are not accurate. As the node and edge weights are obtained by estimation, which is hardly accurate, the approximate models are used. 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.\par
Preemptive scheduling: The preemptive scheduling is prioritized. The highest priority process should always be the process that is currently utilized.\par
Non-Preemptive scheduling: When a process enters the state of running, the state of that process is not deleted from the scheduler until it finishes its service time.\par
The homogeneous computing environment model is a set P of p identical processors connected in a fully connected graph \hyperref[b3]{[4]}. It is also assumed that:\par
Any processor can execute the task and communicate with other processors at the same time.\par
Once a processor has started task execution, it continues without interruption, and on completing the execution it sends immediately the output data to all children tasks in parallel. 
\section[{b) Basic Techniques in DAG Scheduling}]{b) Basic Techniques in DAG Scheduling}\par
Most scheduling algorithms are based on list scheduling. The basic idea of list scheduling is to assign priorities to the nodes of DAG, then place the nodes in a list called ready list according to the priority levels and then lastly map the nodes onto the processors in the order of priority. A higher priority node will be examined first for scheduling before a node with a lower priority. In case any two or more nodes have the same priority, then the ties are needed to be break using some useful method. There are various ways to determine the priorities of nodes such as HLF (Highest level First), LP (Longest Path), LPT (Longest Processing Time) and CP (Critical Path).Frequently used attributes for assigning priority are \hyperref[b1]{[2]}[4] \hyperref[b4]{[5]}:t-level: t-level(Top Level) of the node ni in DAG is the length of the longest path from entry node to ni (excluding ni) i.e. the sum of all the nodes computational costs and edges weights along the path.\par
b-level: The b-level (Bottom Level)of a node ni is the length of the longest path from node ni to an exit node . The b-level is computed recursively by traversing the DAG upward starting from the exit node.\par
Static level: Some scheduling algorithms do not consider the edge weights in computing the b-level known as static b-level. or static level.\par
ALAP 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
CP (Critical Path):It is the length of the longest path from entry node to the exit node A DAG can have more than one CP. b-level of a node is bounded by the length of a critical path.\par
EST (Earliest Starting Time): Procedure for computing the t-levels can also be used to compute the EST of nodes. The other name for EST is ASAP (As-Soon-As-Possible) start-time.\par
A DAG -G = (V, E, w, c) -that represents the application to be scheduled  
\section[{Bnp scheduling algorithms}]{Bnp scheduling algorithms}\par
In this section, we discuss four basic BNP scheduling algorithms: HLFET, ISH, MCP, and ETF. All these algorithms are for a limited number of homogeneous processors. The major characteristics of these algorithms are summarized in Table \hyperref[tab_0]{1} \hyperref[b5]{[6]}. In table, p denotes the number of processors given.     
\section[{Performance Results and Comparison}]{Performance Results and Comparison}\par
In this section, we present the performance results and comparisons of the 4 BNP scheduling algorithms discussed above. The comparisons are based upon the following four comparison metrics \hyperref[b1]{[2]}[4]: 1. 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. 2. Speed Up: The Speed Up value is computed by dividing the sequential execution time by the parallel execution time.\par
1) Calculate the static b-level of each node.\par
2) Make a ready list in a descending order of static b-level. Initially, the ready list contains only the entry nodes. Ties are broken randomly. Repeat 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. 
\section[{1) Calculate the static b-level of each node.}]{1) Calculate the static b-level of each node.}\par
2) Make a ready list in a descending order of static b-level. Initially, the ready list contains only the entry nodes. Ties are broken randomly. Repeat 3) Schedule the first node in the ready list to the processor that allows the earliest execution, using the non-insertion algorithm. 4) If scheduling of this node causes an idle time slot, then find as many nodes as possible from the ready list that can be scheduled to the idle time slot but cannot be scheduled earlier on other processors. 5) Update the ready list by inserting the nodes that are now ready. Until all nodes are scheduled 1) Compute the ALAP time of each node.\par
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 lexicographical 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. 
\section[{1) Compute the static b-level of each node.}]{1) Compute the static b-level of each node.}\par
2) Initially, the pool of ready nodes includes only the entry nodes. Repeat 3) Calculate the earliest start-time on each processor for each node in the ready pool. Pick the node-processor 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.         So it can be concluded that for small number of tasks (35) MCP is the best algorithm but, with increasing number of tasks (50 \& 65) ISH is one of the efficient algorithm, considering the data gathered using the scenarios and the performance calculated from them.\par
Future Scope: A lot of work can be done considering more case scenarios:\par
The number of tasks can be changed to create test case scenarios. Heterogeneous environment can be considered. \begin{figure}[htbp]
\noindent\textbf{1}\includegraphics[]{image-2.png}
\caption{\label{fig_0}Fig. 1 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-3.png}
\caption{\label{fig_1}V}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{2}\includegraphics[]{image-4.png}
\caption{\label{fig_2}Fig. 2 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{3}\includegraphics[]{image-5.png}
\caption{\label{fig_3}Fig. 3 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{455}\includegraphics[]{image-6.png}
\caption{\label{fig_4}Fig. 4 : 5 .Fig. 5 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{3}\includegraphics[]{image-7.png}
\caption{\label{fig_5}3 .}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{6}\includegraphics[]{image-8.png}
\caption{\label{fig_6}Fig. 6 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{89}\includegraphics[]{image-9.png}
\caption{\label{fig_7}Fig. 8 :Fig. 9 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{101112}\includegraphics[]{image-10.png}
\caption{\label{fig_8}Fig. 10 :Fig. 11 :Fig. 12 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{14}\includegraphics[]{image-11.png}
\caption{\label{fig_9}Fig. 14 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{151718}\includegraphics[]{image-12.png}
\caption{\label{fig_10}Fig. 15 :Fig. 17 :Fig. 18 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{1920}\includegraphics[]{image-13.png}
\caption{\label{fig_11}Fig. 19 :Fig. 20 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{}\includegraphics[]{image-14.png}
\caption{\label{fig_12}Both}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{1} \par 
\begin{longtable}{P{0.10077319587628865\textwidth}P{0.43814432989690716\textwidth}P{0.1533505154639175\textwidth}P{0.10515463917525773\textwidth}P{0.05257731958762887\textwidth}}
Algorithm\tabcellsep Proposed by[year]\tabcellsep \multicolumn{3}{l}{Priority List Type Greedy}\\
HLFET\tabcellsep Adam et al. [1974]\tabcellsep SL\tabcellsep Static\tabcellsep Yes\\
ISH\tabcellsep Kruatrachue \& Lewis [1987]\tabcellsep SL\tabcellsep Static\tabcellsep Yes\\
MCP\tabcellsep Wu \& Gajski [1990]\tabcellsep ALAP\tabcellsep Static\tabcellsep Yes\\
ETF\tabcellsep Hwang et al. [1989]\tabcellsep SL\tabcellsep Static\tabcellsep Yes\end{longtable} \par
  {\small\itshape [Note: a) The HLFET (Highest Level First with Estimated Times) Algorithm\hyperref[b12]{[12]}: It is one of the simplest scheduling algorithms. The algorithm is briefly described below in Fig.2.]} 
\caption{\label{tab_0}Table 1 :}\end{figure}
 \begin{figure}[htbp]
\noindent\textbf{} \par 
\begin{longtable}{P{0.20173333333333335\textwidth}P{0.026066666666666665\textwidth}P{0.08273333333333333\textwidth}P{0.026066666666666665\textwidth}P{0.5043333333333334\textwidth}P{0.009066666666666666\textwidth}}
\tabcellsep 350\tabcellsep \tabcellsep \\
\tabcellsep 300\tabcellsep \tabcellsep \\
Speed Up\tabcellsep 200 250\tabcellsep \tabcellsep \tabcellsep HLFET\\
Average\tabcellsep 100 150\tabcellsep \tabcellsep \tabcellsep MCP ETF\\
\tabcellsep 50\tabcellsep \tabcellsep \tabcellsep ISH\\
\tabcellsep 0\tabcellsep \tabcellsep \\
\tabcellsep \tabcellsep 35\tabcellsep 50 Number Of Task Nodes\tabcellsep 65\tabcellsep 2012\\
\multicolumn{5}{l}{Fig. 21 : Graph representing Speedup of Algorithms}\tabcellsep Year\\
\multicolumn{5}{l}{When the tasks are 35, The MCP algorithm yields}\\
\multicolumn{5}{l}{highest Speedup value and ISH gives lowest}\\
\multicolumn{3}{l}{speedup.}\tabcellsep \\
\multicolumn{2}{l}{VI.}\tabcellsep \multicolumn{3}{l}{Conclusion and Future Scope}\\
\tabcellsep \tabcellsep \multicolumn{3}{l}{After Comparative analysis following results}\\
\multicolumn{3}{l}{were derived:}\tabcellsep \\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep D D D D ) A\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep (\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep With 35 task nodes, the MCP algorithm gives lowest\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep SLR value with ISH algorithm giving highest SLR\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep value.\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep With 50 tasks, the ISH shows the lowest SLR value\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep and HLFET gives highest SLR value.\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep With 65 tasks, the ISH has the lesser SLR values\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep and ETF gives highest value.\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep d) Average Speedup: Higher the value of Speedup,\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep more efficient is the algorithm. Fig. 21 shows the\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep Speedup of the all 4 algorithms with various nodes\\
\tabcellsep \tabcellsep \tabcellsep \tabcellsep cases.\end{longtable} \par
 
\caption{\label{tab_2}}\end{figure}
 			\footnote{© 2012 Global Journals Inc. (US)Global Journal of Computer Science and Technology} 		 		\backmatter  			  				\begin{bibitemlist}{1}
\bibitem[Parallelism and Scalability ()]{b8}\label{b8} 	 		\textit{},  		 			Parallelism 		,  		 			Programmability Scalability 		.  		1993. NY: Mc Graw Hill.  	 
\bibitem[Adam et al. (1974)]{b11}\label{b11} 	 		‘A Comparison of List Scheduling for Parallel Processing Systems’.  		 			T L Adam 		,  		 			K Chandy 		,  		 			J Dickson 		.  	 	 		\textit{Communications of the ACM}  		Dec.1974. 17  (12)  p. .  	 
\bibitem[Sharma et al. (2012)]{b9}\label{b9} 	 		‘A STUDY OF BNP PARALLEL TASK SCHEDULING ALGORITHMS METRIC'S FOR DISTRIBUTED DATABASE SYSTEM’.  		 			Manik Sharma 		,  		 			Dr 		,  		 			Gurdev Singh 		,  		 			Harsimran Kaur 		.  	 	 		\textit{International Journal of Distributed and Parallel Systems (IJDPS)}  		January 2012. 3  (1) .  	 
\bibitem[Hwang]{b7}\label{b7} 	 		\textit{Advanced Computer Architecture},  		 			K Hwang 		.  		 	 
\bibitem[Lenstra and Kan (1981)]{b10}\label{b10} 	 		‘An Introduction to multiprocessor Scheduling Algorithm’.  		 			J K Lenstra 		,  		 			A H G Kan 		.  	 	 		\textit{Questi}  		March 1981. 5.  	 
\bibitem[Kaur et al.]{b1}\label{b1} 	 		‘Analysis Comparison and Performance Evaluation of BNP Scheduling Algorithm in parallel Processing’.  		 			Parneet Kaur 		,  		 			Dheerandra Singh 		,  		 			Gurvinder Singh 		.  	 	 		\textit{International journal of Knowledge engineering}  		 	 
\bibitem[Ahmad et al. ()]{b4}\label{b4} 	 		\textit{Analysis, Evaluation, and Comparison of Algorithms for Scheduling Task Graphs on Parallel Processors},  		 			Ishfaq Ahmad 		,  		 			Yu-Kwong Kwok 		,  		 			Min-You Wu 		.  		1996. IEEE. p. .  	 
\bibitem[Kwok and Ahmed ()]{b5}\label{b5} 	 		‘Benchmarking the Task Graph Scheduling Algorithms’.  		 			Y Kwok 		,  		 			I Ahmed 		.  	 	 		\textit{Proc. IPPS/SPDP},  				 (IPPS/SPDP)  		1998.  	 
\bibitem[Droro et al.]{b0}\label{b0} 	 		 			G Droro 		,  		 			Larry Feitelson 		,  		 			Uwe Rudolph 		,  		 			Kenneth C Schwiegelshohn 		,  		 			Parkson Sevcik 		,  		 			Wong 		.  		\textit{Theory and Practice in Parallel Job Scheduling},  				 	 
\bibitem[Barney]{b6}\label{b6} 	 		\textit{Introduction to Parallel Computing},  		 			Blaise Barney 		.  		 		 			Lawrence Livermore National Laboratory 		 	 
\bibitem[Ahmad et al.]{b2}\label{b2} 	 		\textit{Performance Comparison of Algorithms for Static scheduling of DAG to Multi-processors},  		 			Ishfaq Ahmad 		,  		 			Yu-Kwong Kwok 		,  		 			Min-You Wu 		.  		 \url{http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.8979\&rep=rep1\&type=pdf}  		 	 
\bibitem[Kwok and Ahmad (1999)]{b12}\label{b12} 	 		‘Static Scheduling Algorithm for Allocating Directed Task Graph to multiprocessors’.  		 			Yu-Kwong Kwok 		,  		 			Ishfaq Ahmad 		.  	 	 		\textit{ACM Computing Surveys}  		December 1999. 31  (4) .  	 
\bibitem[Hagras and Janecek ()]{b3}\label{b3} 	 		‘Static versus Dynamic List-Scheduling Performance Comparison’.  		 			T Hagras 		,  		 			J Janecek 		.  	 	 		\textit{Acta Polytechnica}  		2003. 43  (6) .  	 
\end{bibitemlist}
 			 		 	 
\end{document}
