Click for new scientific resources and news about Corona[COVID-19]

Paper Information

Journal:   JOURNAL OF SOFT COMPUTING AND INFORMATION TECHNOLOGY (JSCIT)   FALL 2016 , Volume 5 , Number 3 ; Page(s) 35 To 54.
 
Paper: 

AN EFFICIENT HYBRID APPROACH BASED ON THE ACO AND CLA FOR STATIC TASK-GRAPH SCHEDULING IN HOMOGENEOUS MULTIPROCESSOR ENVIRONMENTS

 
 
Author(s):  BOVEIRI HAMID REZA*
 
* SAMA TECHNICAL AND VOCATIONAL COLLEGE, ISLAMIC AZAD UNIVERSITY, SHOUSHTAR BRANCH, SHOUSHTAR, IRAN
 
Abstract: 

Task scheduling has been so far of important challenges in high-performance computers e.g. parallel and distributed systems. Using such architectures during compiling, each application program is divided to some tasks. Because of data-flow among the tasks, they may be dependent to one another; hence, there will be precedence constraints and communication delays among them so that each application with its corresponding tasks can be modeled using a Directed Acyclic Graph (DAG) named task graph. In static task-graph scheduling in homogeneous multiprocessor environments, tasks in the given task graph should be mapped to a predefined number of identical processing elements regarding the precedence constraints and communication delays so that the program’s completion time (finish time) is minimized, and this is an NP-hard problem form the time-complexity perspective. Actually, the achieved results are dominated by two different-in-nature factors: 1) which topological order of tasks should be considered? (sequencing subproblem), and 2) how should the extracted order be distributed over the processors? (assigning subproblem). In this paper, an efficient hybrid approach is proposed in which the Ant Colony Optimization (ACO) determines the order of tasks, and a Cellular Learning Automata (CLA) machine tackles with the assigning subproblem, and maps the task order derived by ACO to the existing processors.125 randomly-generated task graphs with different shape parameters such as size, Communication-to-Computation Ratio (CCR), and parallelism are used for the comparison study, and the results shows that the proposed approach is more successful than the traditional counterparts from the performance point of view, and eventually outperforms them.

 
Keyword(s): ANT COLONY OPTIMIZATION (ACO), CELLULAR LEARNING AUTOMATA (CLA), META-HEURISTICS, MULTIPROCESSOR TASK-GRAPH SCHEDULING, PARALLEL AND DISTRIBUTED SYSTEMS
 
 
References: 
  • Not Registered.
  •  
 
+ Click to Cite.
APA: Copy

BOVEIRI, H. (2016). AN EFFICIENT HYBRID APPROACH BASED ON THE ACO AND CLA FOR STATIC TASK-GRAPH SCHEDULING IN HOMOGENEOUS MULTIPROCESSOR ENVIRONMENTS. JOURNAL OF SOFT COMPUTING AND INFORMATION TECHNOLOGY (JSCIT), 5(3 ), 35-54. https://www.sid.ir/en/journal/ViewPaper.aspx?id=570765



Vancouver: Copy

BOVEIRI HAMID REZA. AN EFFICIENT HYBRID APPROACH BASED ON THE ACO AND CLA FOR STATIC TASK-GRAPH SCHEDULING IN HOMOGENEOUS MULTIPROCESSOR ENVIRONMENTS. JOURNAL OF SOFT COMPUTING AND INFORMATION TECHNOLOGY (JSCIT). 2016 [cited 2021May16];5(3 ):35-54. Available from: https://www.sid.ir/en/journal/ViewPaper.aspx?id=570765



IEEE: Copy

BOVEIRI, H., 2016. AN EFFICIENT HYBRID APPROACH BASED ON THE ACO AND CLA FOR STATIC TASK-GRAPH SCHEDULING IN HOMOGENEOUS MULTIPROCESSOR ENVIRONMENTS. JOURNAL OF SOFT COMPUTING AND INFORMATION TECHNOLOGY (JSCIT), [online] 5(3 ), pp.35-54. Available: https://www.sid.ir/en/journal/ViewPaper.aspx?id=570765.



 
 
Persian Abstract Yearly Visit 41
 
Latest on Blog
Enter SID Blog