Evaluation of Gauss Rules with a Centralised
Dynamic Load Balancing Technique
in Parallel Computing Systems
FESTUS OMONIGHO IYUKE & BAHARI IDRUS
ABSTRACT
Evaluation of Gauss rules with a centralised dynamic load balancing technique under PVM-based environment in approximating one-dimensional definite integrals on parallel computing systems is described. Gauss rules are normally applied in pairs, so that both an approximation to the integral and an estimate of the error in the approximation can be evaluated together. It is usual to subdivide the range of integration into n subintervals, and these rules are applied separately to each of these subintervals. The aim is to satisfy the accuracy requirement (this is assured if the sum of the estimated absolute errors across the n subintervals is less than absolute accuracy, ∈) whilst keeping the number of evaluations of the integrand to a minimum. The load balancing operation is realised by initialising a centralised pool of task from which a workload (subintervals) to be performed is distributed to the various contending slave processors. Besides, the centralised pool of task technique involved master-slave relationship, where a master processor engaged in interval decomposition into n subintervals. Subsequently, these subintervals are distributed to the slave processors to ensure a workload balanced state is attained. Whenever a slave processor completes its subinterval computation, the partially approximated results are returned to the master. By way of reducing the communication overhead, that would have been associated with the integral evaluation process. The effectiveness of the approach used in connection with the novel workload management scheme is demonstrated in the result obtained and the global workload optimisation for the tested application problems.
ABSTRAK
Kertas ini membincangkan tentang Petua Gauss dengan teknik pengimbangan muatan dinamik terpusat bagi persekitaran berasaskan PVM dalam menganggarkan pengamiran tentu satu dimensi pada sistem pengkomputeran selari. Petua Gauss pada kebiasaannya dilaksanakan secara berpasangan
supaya penganggaran kamiran serta ralat pada penganggaran tersebut dapat dinilai bersama. Julat pengamiran dibahagikan kepada n bilangan sub-selang dengan setiap peraturan dalam petua ini akan dilaksanakan secara berasingan bagi setiap sub-selang ini. Matlamatnya adalah bagi memastikan keperluan kejituan dipenuhi (ini dapat ditentukan sekiranya jumlah anggaran ralat mutlak bagi n sub-selang kurang daripada kejituan mutlak, ∈), dalam masa yang sama memastikan bilangan penilaian kamiran berada pada tahap minimum. Operasi pengimbangan muatan dilakukan dengan memusatkan kumpulan kerja yang mana setiap beban tugas subselang diagihkan kepada pemproses-pemproses kecil (slave processors). Selain daripada itu, teknik kumpulan kerja berpusat turut melibatkan hubungan
di antara pemproses utama dan beberapa pemproses kecil (master-slave relationship), yang mana pemproses utama dihuraikan kepada beberapa n sub-selang. Kemudian, kesemua sub-selang ini akan diagihkan pula kepada pemproses-pemproses kecil sehingga tahap beban yang seimbang dicapai.
Apabila pemproses kecil selesai melaksanakan pengiraan sub-selang, sebahagian hasil anggaran dihantar ke pemproses utama. Melalui pengurangan overhed komunikasi, ini telah diambil kira dalam proses penilaian pengamiran. Keberkesanan pendekatan yang digunakan bersama dengan skema pengurusan muatan ditunjukkan dalam dapatan kajian serta keputusan yang diperolehi melalui beban tugas yang optimum bagi masalah aplikasi yang diuji.
