Evaluation of Allocation Algorithms for Mesh-structured Systems via Multistage Simulation

L. Koszalka (Poland)


Mesh-structured system, allocation algorithm, simulation, parallel and distributed computing systems


In multicomputers and computer networks a proper processor allocation of incoming jobs has a big impact on efficiency of parallel and distributed computing. In this paper, the mesh topology and allocation with using First Fit (FF) and Stack-Based (SBA) schemes, are considered. In particular, the proposed algorithms, called SSBA (Stack-Based with Sorting) and BFSBA (Better Fit Stack Based) are described. Evaluation of algorithm's properties have been done with using the proposed experimentation system. This system consists of such modules like experiment design, visualization of allocation processes, presentation of results of series of experiments (including computing the introduced measures of efficiency). The investigations, carried out in this system, show advantages of the proposed algorithms: SSBA is faster, and BFSBA causes less fragmentation than the classic SBA. Moreover, SBA-family algorithms are much more efficient than FF algorithm.

Important Links:

Go Back