Processor Allocation Two-Dimensional Mesh-Based Multi-Computer Systems: Protecting against Over-Partitioning and Maintaining Certain System Utilization Level

Abstract

Gradual Request-Partitioning-Based (GRPB) processor allocation strategies try to remedy the problem internal fragmentation by having requests get be allocated non-contiguously in the form of gradually produced blocks in case contiguous allocation is not possible. In this article, we experimentally show that GRPB techniques suffer from the problem of over-partitioning, and thus, negatively affects key performance indicators of multi-computer systems. This paper also proposes a framework for using fuzzy logic to control specific key performance levels in two-dimensional mesh-based multi-computer systems. We demonstrated that it is possible to implement a fuzzy-based feedback control system to control a number of performance indicators in the parallel system. The proposed allocation scheme prevents over-splitting of parallel jobs by forcefully limit to the maximum number of blocks that can be assigned to any parallel job. This maximum number is referred to as the partitioning-bound. Preventing parallel processes from getting over-partitioned is vitally important as this (i) reduces the distance of inter-processor source-to-destination communication and (ii) helps in avoiding the “inter-process interference”; the main cause of communication contention. Fuzzy-based allocation provides a mechanism to dynamically control the partitioning-bound. Instead of pre-setting and having a fixed partitioning-bound level, we provide a way to set this value at run time taking into consideration the current status to multi-computer system.

Keywords: Fuzzy-control, Gradual request-partitioning, Internal fragmentation, Multi-computer systems, Non-contiguous processor allocation.

View PDF