Improving the Balance of a Random-access Data Structure on a Migratory Thread Platform

Abstract

In this work, we look at a distributed random-access data structure provided with a migratory-thread platform: the Lucata Pathfinder, called a chunked array. A chunked array provides sequential locality on sections of the array while having its memory distributed. We consider drawbacks of the implementation of this structure in terms of balancing the distribution of its elements. We provide an alternate implementation with better balancing, which can simplify algorithms like a distributed sort. We show analytically that our implementation balances significantly better for smaller numbers of elements, but the improvement declines proportionally to the number of elements. Finally, we test our implementation in a simulator and show that the balancing of the elements also leads to good balancing of execution.