Dynamic Multiprocessor Scheduling Model For The Reconfigurable Mesh Computing Networks
Task scheduling is a combinatorial optimisation problem that is known to have large interacting degrees of freedom and is generally classified as NP-complete. Most solutions to the problem have been proposed in the form of heuristics. These include approaches using list scheduling, queueing theory,...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Penerbit UTM Press
2002
|
| Subjects: | |
| Online Access: | http://eprints.utm.my/1428/1/JT37C5.pdf |
| _version_ | 1796853239220535296 |
|---|---|
| author | Salleh, Shaharuddin Aziz, Nur Arina Bazilah Azmee, Nor Afzalina Mohamed, Nurul Huda |
| author_facet | Salleh, Shaharuddin Aziz, Nur Arina Bazilah Azmee, Nor Afzalina Mohamed, Nurul Huda |
| author_sort | Salleh, Shaharuddin |
| collection | ePrints |
| description | Task scheduling is a combinatorial optimisation problem that is known to have large interacting degrees of freedom and is generally classified as NP-complete. Most solutions to the problem have been proposed in the form of heuristics. These include approaches using list scheduling, queueing theory, graph theoretic and enumerated search. In this paper, we present a dynamic scheduling method for mapping tasks onto a set of processing elements (PEs) on the reconfigurable mesh parallel computing model. Our model called the Dynamic Scheduler on Reconfigurable Mesh (DSRM) is based on the Markovian m/m/c queueing system, where tasks arrive and form a queue according to Poisson distribution, and are serviced according to the exponential distribution. The main objective in our study is to produce a schedule that distributes the tasks fairly by balancing the load on all PEs. The second objective is to produce a high rate of successfully assigned tasks on the PEs. These two requirements tend to conflict and they constitute the maximum-minimum problem in optimisation, where the maximum of one causes the other to be minimum. We study the effectiveness of our approach in dealing with these two requirements in DSRM. |
| first_indexed | 2024-03-05T17:56:38Z |
| format | Article |
| id | utm.eprints-1428 |
| institution | Universiti Teknologi Malaysia - ePrints |
| language | English |
| last_indexed | 2024-03-05T17:56:38Z |
| publishDate | 2002 |
| publisher | Penerbit UTM Press |
| record_format | dspace |
| spelling | utm.eprints-14282017-11-01T04:17:43Z http://eprints.utm.my/1428/ Dynamic Multiprocessor Scheduling Model For The Reconfigurable Mesh Computing Networks Salleh, Shaharuddin Aziz, Nur Arina Bazilah Azmee, Nor Afzalina Mohamed, Nurul Huda QA Mathematics Task scheduling is a combinatorial optimisation problem that is known to have large interacting degrees of freedom and is generally classified as NP-complete. Most solutions to the problem have been proposed in the form of heuristics. These include approaches using list scheduling, queueing theory, graph theoretic and enumerated search. In this paper, we present a dynamic scheduling method for mapping tasks onto a set of processing elements (PEs) on the reconfigurable mesh parallel computing model. Our model called the Dynamic Scheduler on Reconfigurable Mesh (DSRM) is based on the Markovian m/m/c queueing system, where tasks arrive and form a queue according to Poisson distribution, and are serviced according to the exponential distribution. The main objective in our study is to produce a schedule that distributes the tasks fairly by balancing the load on all PEs. The second objective is to produce a high rate of successfully assigned tasks on the PEs. These two requirements tend to conflict and they constitute the maximum-minimum problem in optimisation, where the maximum of one causes the other to be minimum. We study the effectiveness of our approach in dealing with these two requirements in DSRM. Penerbit UTM Press 2002-12 Article PeerReviewed application/pdf en http://eprints.utm.my/1428/1/JT37C5.pdf Salleh, Shaharuddin and Aziz, Nur Arina Bazilah and Azmee, Nor Afzalina and Mohamed, Nurul Huda (2002) Dynamic Multiprocessor Scheduling Model For The Reconfigurable Mesh Computing Networks. Jurnal Teknologi C (37C). pp. 55-66. ISSN 0127-9696 http://www.penerbit.utm.my/onlinejournal/37/C/JT37C5.pdf |
| spellingShingle | QA Mathematics Salleh, Shaharuddin Aziz, Nur Arina Bazilah Azmee, Nor Afzalina Mohamed, Nurul Huda Dynamic Multiprocessor Scheduling Model For The Reconfigurable Mesh Computing Networks |
| title | Dynamic Multiprocessor Scheduling Model For The Reconfigurable Mesh Computing Networks |
| title_full | Dynamic Multiprocessor Scheduling Model For The Reconfigurable Mesh Computing Networks |
| title_fullStr | Dynamic Multiprocessor Scheduling Model For The Reconfigurable Mesh Computing Networks |
| title_full_unstemmed | Dynamic Multiprocessor Scheduling Model For The Reconfigurable Mesh Computing Networks |
| title_short | Dynamic Multiprocessor Scheduling Model For The Reconfigurable Mesh Computing Networks |
| title_sort | dynamic multiprocessor scheduling model for the reconfigurable mesh computing networks |
| topic | QA Mathematics |
| url | http://eprints.utm.my/1428/1/JT37C5.pdf |
| work_keys_str_mv | AT sallehshaharuddin dynamicmultiprocessorschedulingmodelforthereconfigurablemeshcomputingnetworks AT aziznurarinabazilah dynamicmultiprocessorschedulingmodelforthereconfigurablemeshcomputingnetworks AT azmeenorafzalina dynamicmultiprocessorschedulingmodelforthereconfigurablemeshcomputingnetworks AT mohamednurulhuda dynamicmultiprocessorschedulingmodelforthereconfigurablemeshcomputingnetworks |