Cluster queue structure for shared-memory multiprocessor systems

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.