Home // ADVCOMP 2010, The Fourth International Conference on Advanced Engineering Computing and Applications in Sciences // View article

Submesh Allocation in 2D-Mesh Multicomputers: Partitioning at the Longest Dimension of Requests

Authors:
Sulieman Bani-Ahmad

Keywords: Multicomputer; 2D mesh; Non-contiguous Allocation; Request Partitioning

Abstract:
Two adaptive noncontiguous allocation strategies for 2D-mesh multicomputers are proposed in this paper. The first is first-fit-based and the second is best-fit-based. That is; for a given request, the proposed first-fit-based approach tries to find a free submesh using the well-known first-fit strategy, if it fails, the request at hand is partitioned into two sub-requests that are allocated using the first-fit approach. Partitioning is performed at the longest dimension of the request. That is, for a given request of size axß and assuming ß>a, the two partition-sizes are ax(ß-1) and ax1 after removing one from the longest dimension of the request. The two new sub-requests are then allocated using the first-fit strategy. This procedure continues recursively until the request is fulfilled. The second approach is also based on PArtitioning at the Longest Dimension (PALD) of requests but a best-fit approach is used to allocate requests and sub-requests. The partitioning mechanism aims at (i) lifting the condition of contiguity, and (ii) at the same time maintaining good level of contiguity. Removing one from the longest dimension of a request is expected to produce two sub-requests one of which is relatively big and as close as possible to the square-shape and, thus; reducing communication latency caused by non-contiguity. Using extensive simulations, we evaluated the proposed strategies and compared them with previous contiguous and non-contiguous strategies. Simulation outcomes clearly show the proposed PALD-based schemes produce the best Average Response Time (ART), the Average System Utilization (ASU) and also produce relatively low communication overhead.

Pages: 99 to 104

Copyright: Copyright (c) IARIA, 2010

Publication date: October 25, 2010

Published in: conference

ISSN: 2308-4499

ISBN: 978-1-61208-101-4

Location: Florence, Italy

Dates: from October 25, 2010 to October 30, 2010