A task allocation scheme for hypercube distributed computing systems using the affinity graph model

A task allocation algorithm is presented which is based on the affinity graph model for hypercube distributed computing systems. In the affinity graph model, the vertices represent the modules in the task to be allocated. The weight of the edges represents the affinity the modules represented by the vertices have for each other. The affinity function has been defined in such a way that both the competing demands of load balancing and minimizing interprocessor communication are addressed. By applying a graph partitioning algorithm on such an affinity graph, optimal task allocation is possible. The task allocation algorithm presented for hypercube distributed computing systems uses the above idea to repeatedly partition the affinity graph until all modules in the task are allocated. The algorithm is fully distributed with no central control being exercised.