{'fraction_non_alphanumeric': 0.0192896509491733, 'fraction_numerical': 0.0, 'mean_word_length': 5.3313953488372094, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Locality-aware Load Balancing for Dynamic and Irregular Computations

Development of scalable application codes is a challenging task. It requires an understanding of system architecture, programming model, and ability to identify and express parallelism in the underlying problem. Design patterns can help programmers by presenting a set of recipes for expressing and implementing parallelism in the context of a particular programming model and classes of algorithms. In the current paper, we consider the Global Arrays shared memory programming model. In particular, we focus on a relatively common design pattern associated with implementations of dynamic load balancing in GA programs. Dynamic load balancing is often used in dynamic and irregular problems that have been parallelized using GA, in different application areas such as the electronic structure, molecular dynamics, or computational physics based on adaptive mesh refinement. The global/shared view of data and efficient one-sided communication offered by the GA toolkit facilitate a relatively straightforward implementation of dynamic load balancing, as compared to MPI. In particular, the programmer can take advantage of atomic operations such as fetch-and-add to schedule the execution of parallel tasks and rely on one-sided access to shared data to implement communication involved in executing individual tasks, regardless of the data ownership. For example, a common design pattern used in several computational chemistry algorithms uses an atomic update of a shared variable that corresponds to the current task index, pointing to either an explicit or implicit task list: a get for accessing the required sections of global arrays, followed by calculation, and then updating the result array using a put or atomic accumulate operation. The decoupling of the underlying data placement from computation makes the implementation of algorithms relying on dynamic load balancing relatively simple to even a non-expert users. However, it does not address the problem of efficient scheduling of tasks, and locality optimizations that are required to maximize performance, taking into account the architectural details such as network topology, latency and bandwidth, and other factors such as the communication contention in access to the required data. The computational structure in these problems is often expressible as directed acyclic graphs (DAG). Each node in the graph represents a task or a work element and edges represent input-output relationships. Each node can be executed only after all nodes with edges incident on it have been processed. When there are independent paths through the graph, the computation is said to exhibit inter-task parallelism, and more than one task can be executed in parallel. In this paper, we propose a work-sharing construct to schedule the DAG on a parallel system, to minimize the overall execution time. We consider two work-sharing models. In the static work-sharing model, the DAG is completely specified before it is processed. Alternatively, the dynamic work-sharing model allows dynamic addition of tasks, as the DAG is being processed. While the static work-sharing model facilitates global scheduling decisions, the dynamic model provides