Title:
|
AI GAME PLAYING APPROACH FOR FAST PROCESSOR ALLOCATION IN HYPERCUBE SYSTEMS USING VEITCH DIAGRAM |
Author(s):
|
Srinivasan T , Srikanth Pjs , Praveen K , Harish Subramaniam L |
ISBN:
|
ISSN: 1646-3692 |
Editors:
|
Pedro Isaías and Marcin Paprzycki |
Year:
|
2006 |
Edition:
|
V I, 1 |
Keywords:
|
External / Internal Fragmentation, Graph Coloring, Hypercube, Incomplete subcube, Veitch diagram, Penalty Factor, Processor Allocation / Deallocation, AI G |
Type:
|
Journal Paper |
First Page:
|
57 |
Last Page:
|
72 |
Language:
|
English |
Cover:
|
|
Full Contents:
|
click to dowload
|
Paper Abstract:
|
In this journal, we present a method called AI Game Playing Approach for Fast Processor Allocation in Hypercube Systems using Veitch diagram (AIPA) which achieves a fast and complete subcube recognition with a complexity that is far less than that of Gray Code (GC), Buddy, Modified Buddy, Modified Gray Code, Free List, Heuristic Processor Allocation (HPA), Tree Collapsing (TC) and other existing allocation policies. The crux of the strategy is to identify a free subcube that can fit the Veitch diagram (also called as the Karnaugh map or K-map). The cells in the Veitch diagram attribute the processors. An AI Game playing approach is applied to ensure optimality along with a graph coloring approach with a resultant penalty factor computation, for effective implementation of the strategy. The algorithm deals with cubic as well as non-cubic allocation and is not only statically optimal but also optimal in a dynamic environment. Extensive performance analysis has been carried out with outcomes discussed comparatively with other allocation strategies. It is shown that our approach supersedes many others in terms of allocation and deallocation costs. The algorithm is also efficient in memory utilization and minimization of system fragmentation. Moreover, the simulation results illustrate that the AIPA strategy significantly improves performance. |
|
|
|
|