Cluster queue structure for shared-memory multiprocessor systems

Weiping Zhu, Tyngyeu Liang, Ce-Kuen Shieh

Research output: Contribution to conferencePaper

2 Citations (Scopus)

Abstract

Three basic organizations have been proposed to construct the task queues for a shared-memory multiprocess system: centralized, distributed, and hierarchical structures. The centralized structure is not suitable for massively parallel systems since the centralized queue is a bottleneck. The distributed structure, on the other hand, will end up with load imbalancing due to the random execution time of tasks. The hierarchical structure tends to combine the advantage of the previous two structures and reduces the impact of bottleneck and load imbalancing. However, we found out the load imbalancing still exists in the hierarchical structure. It also affects system performance, in particular, when the workload become heavier. We further identified the cause of this problem. We then propose the use of a forest structure to provide load balancing and contention minimization.

Original languageEnglish
Pages420-427
Number of pages8
Publication statusPublished - 1998 Dec 1
EventProceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS - Tainan, China
Duration: 1998 Dec 141998 Dec 16

Other

OtherProceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS
CityTainan, China
Period98-12-1498-12-16

Fingerprint

Resource allocation
Data storage equipment

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this

Zhu, W., Liang, T., & Shieh, C-K. (1998). Cluster queue structure for shared-memory multiprocessor systems. 420-427. Paper presented at Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS, Tainan, China, .
Zhu, Weiping ; Liang, Tyngyeu ; Shieh, Ce-Kuen. / Cluster queue structure for shared-memory multiprocessor systems. Paper presented at Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS, Tainan, China, .8 p.
@conference{b31f48dd8ffc4b0ab474fbe5c0d55105,
title = "Cluster queue structure for shared-memory multiprocessor systems",
abstract = "Three basic organizations have been proposed to construct the task queues for a shared-memory multiprocess system: centralized, distributed, and hierarchical structures. The centralized structure is not suitable for massively parallel systems since the centralized queue is a bottleneck. The distributed structure, on the other hand, will end up with load imbalancing due to the random execution time of tasks. The hierarchical structure tends to combine the advantage of the previous two structures and reduces the impact of bottleneck and load imbalancing. However, we found out the load imbalancing still exists in the hierarchical structure. It also affects system performance, in particular, when the workload become heavier. We further identified the cause of this problem. We then propose the use of a forest structure to provide load balancing and contention minimization.",
author = "Weiping Zhu and Tyngyeu Liang and Ce-Kuen Shieh",
year = "1998",
month = "12",
day = "1",
language = "English",
pages = "420--427",
note = "Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS ; Conference date: 14-12-1998 Through 16-12-1998",

}

Zhu, W, Liang, T & Shieh, C-K 1998, 'Cluster queue structure for shared-memory multiprocessor systems', Paper presented at Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS, Tainan, China, 98-12-14 - 98-12-16 pp. 420-427.

Cluster queue structure for shared-memory multiprocessor systems. / Zhu, Weiping; Liang, Tyngyeu; Shieh, Ce-Kuen.

1998. 420-427 Paper presented at Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS, Tainan, China, .

Research output: Contribution to conferencePaper

TY - CONF

T1 - Cluster queue structure for shared-memory multiprocessor systems

AU - Zhu, Weiping

AU - Liang, Tyngyeu

AU - Shieh, Ce-Kuen

PY - 1998/12/1

Y1 - 1998/12/1

N2 - Three basic organizations have been proposed to construct the task queues for a shared-memory multiprocess system: centralized, distributed, and hierarchical structures. The centralized structure is not suitable for massively parallel systems since the centralized queue is a bottleneck. The distributed structure, on the other hand, will end up with load imbalancing due to the random execution time of tasks. The hierarchical structure tends to combine the advantage of the previous two structures and reduces the impact of bottleneck and load imbalancing. However, we found out the load imbalancing still exists in the hierarchical structure. It also affects system performance, in particular, when the workload become heavier. We further identified the cause of this problem. We then propose the use of a forest structure to provide load balancing and contention minimization.

AB - Three basic organizations have been proposed to construct the task queues for a shared-memory multiprocess system: centralized, distributed, and hierarchical structures. The centralized structure is not suitable for massively parallel systems since the centralized queue is a bottleneck. The distributed structure, on the other hand, will end up with load imbalancing due to the random execution time of tasks. The hierarchical structure tends to combine the advantage of the previous two structures and reduces the impact of bottleneck and load imbalancing. However, we found out the load imbalancing still exists in the hierarchical structure. It also affects system performance, in particular, when the workload become heavier. We further identified the cause of this problem. We then propose the use of a forest structure to provide load balancing and contention minimization.

UR - http://www.scopus.com/inward/record.url?scp=0032295470&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032295470&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:0032295470

SP - 420

EP - 427

ER -

Zhu W, Liang T, Shieh C-K. Cluster queue structure for shared-memory multiprocessor systems. 1998. Paper presented at Proceedings of the 1998 International Conference on Parallel and Distributed Systems, ICPADS, Tainan, China, .