Allocation algorithms problems in mesh-connected systems

Abstract

Methods of processor allocation described in this paper concentrate on speed and allocation efficiency. Frame Sliding algorithm was used to compare the speed of Improved Stack Based Allocation Algorithm. Improvement of Stack Based Algorithm includes Rotation Optimisation and Task Separation techniques. Also, experimentation system and efficiency coefficients were described. Results of investigations were shown and discussed in this paper.
Authors: Grzegorz CHMAJ, Dawid ZYDEK, Leszek KOSZAŁKA

1. INTRODUCTION

Many computer systems have processors connected with each other by mesh. That kind of connecting is simple to extend and modify. Also, its structure is not complicated, so it can be easily implemented. To improve fit forming jobs (tasks) in that kind of system, the efficient allocation algorithm should be designed. There are many allocation algorithms available [4] and new ones are researched. However, an ideal allocation algorithm is still wanted [3]. Units in mesh are co-operating, so there must be used an algorithm, that will manage their work. System is equipped with tasks queue, where all of tasks waiting for allocation are placed. Allocation algorithm takes tasks from the queue and searches free submesh to allocate them. We assume that tasks are taken from a given queue by order of incoming.

In this paper, two allocation algorithms are compared: Improved Stack Based Algorithm (ISBA) proposed by authors and Frame Sliding Algorithm (FS). Moreover, the original Stack Based Algorithm (SBA) is compared with ISBA-algorithm.

The remainder of this paper is organized as follows: Section 2 describes allocation algorithms. In Section 3 the experimentation system is presented. Section 4 contains research results. Final remarks appear in section 5.