An Efficient Submesh Allocation Scheme Based on Classified Free Submesh List and Task Relocation
Summary :
This paper presents a new submesh allocation scheme for mesh connected multicomputer systems, called CFSL-TR (Classified Free Submesh List-Task Relocation), which reduces task waiting time in two aspects, shortening submesh search time and reducing the submesh allocation delay caused by external fragmentation. This scheme classifies independent free submeshes by their types: square, horizontal rectangle, or vertical rectangle. Then it searches for the best-fit submesh only from one list depending on the type of the given task, thus saving submesh searching time. If no suitable submeshes are found, it is most likely caused by external fragmentation. In such a case, our scheme relocates the tasks being executed to free submeshes and combines the newly available submesh with other fragmented ones to form a larger submesh. This allows allocation of the task, otherwise to be put on the queue, hence reducing the submesh allocation delay. Through simulation, we show that our scheme helps reduce task waiting time and that it is by far more effective to reduce the submesh allocation delay caused by external fragmentation rather than to reduce submesh search time for reduction of the task waiting time.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.6 pp.1454-1462
- Publication Date
- 2004/06/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Papers Selected from 2003 International Technical Conference on Circuits/Systems, Computers and Communications (ITC-CSCC 2003))
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Wonjoo LEE, Changho JEON, "An Efficient Submesh Allocation Scheme Based on Classified Free Submesh List and Task Relocation" in IEICE TRANSACTIONS on Fundamentals,
vol. E87-A, no. 6, pp. 1454-1462, June 2004, doi: .
Abstract: This paper presents a new submesh allocation scheme for mesh connected multicomputer systems, called CFSL-TR (Classified Free Submesh List-Task Relocation), which reduces task waiting time in two aspects, shortening submesh search time and reducing the submesh allocation delay caused by external fragmentation. This scheme classifies independent free submeshes by their types: square, horizontal rectangle, or vertical rectangle. Then it searches for the best-fit submesh only from one list depending on the type of the given task, thus saving submesh searching time. If no suitable submeshes are found, it is most likely caused by external fragmentation. In such a case, our scheme relocates the tasks being executed to free submeshes and combines the newly available submesh with other fragmented ones to form a larger submesh. This allows allocation of the task, otherwise to be put on the queue, hence reducing the submesh allocation delay. Through simulation, we show that our scheme helps reduce task waiting time and that it is by far more effective to reduce the submesh allocation delay caused by external fragmentation rather than to reduce submesh search time for reduction of the task waiting time.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e87-a_6_1454/_p
Copy
@ARTICLE{e87-a_6_1454,
author={Wonjoo LEE, Changho JEON, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Efficient Submesh Allocation Scheme Based on Classified Free Submesh List and Task Relocation},
year={2004},
volume={E87-A},
number={6},
pages={1454-1462},
abstract={This paper presents a new submesh allocation scheme for mesh connected multicomputer systems, called CFSL-TR (Classified Free Submesh List-Task Relocation), which reduces task waiting time in two aspects, shortening submesh search time and reducing the submesh allocation delay caused by external fragmentation. This scheme classifies independent free submeshes by their types: square, horizontal rectangle, or vertical rectangle. Then it searches for the best-fit submesh only from one list depending on the type of the given task, thus saving submesh searching time. If no suitable submeshes are found, it is most likely caused by external fragmentation. In such a case, our scheme relocates the tasks being executed to free submeshes and combines the newly available submesh with other fragmented ones to form a larger submesh. This allows allocation of the task, otherwise to be put on the queue, hence reducing the submesh allocation delay. Through simulation, we show that our scheme helps reduce task waiting time and that it is by far more effective to reduce the submesh allocation delay caused by external fragmentation rather than to reduce submesh search time for reduction of the task waiting time.},
keywords={},
doi={},
ISSN={},
month={June},}
Copy
TY - JOUR
TI - An Efficient Submesh Allocation Scheme Based on Classified Free Submesh List and Task Relocation
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1454
EP - 1462
AU - Wonjoo LEE
AU - Changho JEON
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2004
AB - This paper presents a new submesh allocation scheme for mesh connected multicomputer systems, called CFSL-TR (Classified Free Submesh List-Task Relocation), which reduces task waiting time in two aspects, shortening submesh search time and reducing the submesh allocation delay caused by external fragmentation. This scheme classifies independent free submeshes by their types: square, horizontal rectangle, or vertical rectangle. Then it searches for the best-fit submesh only from one list depending on the type of the given task, thus saving submesh searching time. If no suitable submeshes are found, it is most likely caused by external fragmentation. In such a case, our scheme relocates the tasks being executed to free submeshes and combines the newly available submesh with other fragmented ones to form a larger submesh. This allows allocation of the task, otherwise to be put on the queue, hence reducing the submesh allocation delay. Through simulation, we show that our scheme helps reduce task waiting time and that it is by far more effective to reduce the submesh allocation delay caused by external fragmentation rather than to reduce submesh search time for reduction of the task waiting time.
ER -
English
