ABSTRACT
Nowadays, parallel computing plays a key role in high-performance computing and it is gradually replacing traditional supercomputers. The computing units (processors) in parallel computing systems are linked by different types of networks [1]. The allocation of the computing resources to tasks is a crucial issue in these complex systems. Therefore there is a need to design efficient resource allocation algorithms. Unfortunately, many traditional scheduling algorithms are not able to fulfill this requirement, due to the large amount of data that needs to be transmitted through the network, as well as synchronization and other scheduling overhead required by the processors allotted to the same task. Thus, many parallel task (PT) models have been proposed to address this problem. One of these models is the malleable task (MT) model (sometimes also called moldable task) [2]. This is a promising model that has been used in real application [3]. In the MT model, the processing time of a task depends on the number of processors allotted to it. The communication overhead and synchronization is implicitly included in the processing time. The idea behind the MTs is to provide an alternative strategy to model the communication delays. An MT includes elementary operations (e.g., a numerical routine or a nested loop) with sufficient parallelism to be amenable for multiprocessor processing. Thus, a sequential task can be regarded as a special case of the MT model. The MT model has been used in realistic applications [3,4].
