Dynamic Multiprocessor Scheduling Model for the Reconfigurable Mesh Computing Networks

Abstract

Masalah penjadualan kerja ialah satu masalah pengoptimuman kombinatorik yang diketahui mempunyai darjah kebebasan berinteraksi yang besar. Oleh itu, masalah ini selalunya dikategorikan sebagai NP-lengkap. Kebanyakan penyelesaian bagi masalah ini menggunakan heuristik. Penyelesaiannya termasuk pendekatan berasaskan penjadualan tersenarai, teori giliran, teori graf dan pencaraian berenumerasi. Dalam kertas ini, satu kaedah penjadualan dinamik dicadangkan bagi memeta satu set kerja kepada satu set pemproses dalam rangkaian jaring boleh-konfigurasi. Model kami dipanggil Dynamic Scheduler on Reconfigurable Mesh (DSRM). Model ini berasaskan sistem giliran m/m/c di mana kerja-kerja yang tiba menunggu giliran masing-masing mengikut taburan Poisson, dan diservis mengikut taburan eksponen. Objektif utama dalam kajian ini ialah untuk menghasilkan jadual yang mempunyai taburan kerja seimbang pada pemproses-pemproses. Objektif kedua ialah untuk mempertingkat kadar pengagihan kerja ke tahap maksimum untuk memastikan kejayaan. Kedua-dua objektif ini merupakan satu masalah dikenali sebagai maksimum-minimum, di mana kejayaan dalam satu objektif boleh menyebabkan kemerosotan dalam objektif yang satu lagi. Keberkesanan pendekatan ini dikaji melalui model simulasi DSRM. Kata kunci: Jaring boleh-konfigurasi; penjadualan kerja; pengseimbangan beban dan perkomputeran selari Task scheduling is a combinatorial optimisation problem that is known to have large interacting degrees of freedom and is gerally 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 strudy 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 sucessfully 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. Key words: Reconfigurable mesh; task scheduling; load balancing; and parallel computing