Many parallel applications require periodic redistribution of workloads and associated data. In a distributed memory computer, this redistribution can be difficult if limited memory is available for receiving messages. We propose a model for optimizing the exchange of messages under such circumstances which we call the \it minimum phase remapping problem. We first show that the problem is NP-Complete, and then analyze several methodologies for addressing it. First, we show how the problem can be phrased as an instance of multi-commodity flow. Next, we study a continuous approximation to the problem. We show that this continuous approximation has a solution which requires at most two more phases than the optimal discrete solution, but the question of how to consistently obtain a good discrete solution from the continuous problem remains open. We also devise simple and practical approximation algorithm for the problem with a bound of 1.5 times the optimal number of phases. We also present an empirical study of variations of our algorithms which indicate that our approaches are quite practical.

In many applications of parallel computing, distribution of the data unambiguously implies distribution of work among processors. But there are exceptions where some tasks can be assigned to one of several processors without altering the total volume of communication. In this paper, we study the problem of exploiting this flexibility in assignment of tasks to improve load balance. We first model the problem in terms of network flow and use combinatorial techniques for its solution. Our parametric search algorithms use maximum flow algorithms for probing on a candidate optimal solution value. We describe two algorithms to solve the assignment problem with log W_T and bar P bar probe calls, where W_T and bar P bar, respectively, denote the total workload and number of processors. We also define augmenting paths and cuts for this problem, and show that any algorithm based on augmenting paths can be used to find an optimal solution for the task assignment problem. We then consider a continuous version of the problem, and formulate it as a linearly constrained optimization problem, i.e., min bar Ax bar_infty,; rms.t.; Bx=d. To avoid solving an intractable infty-norm optimization problem, we show that in this case minimizing the 2-norm is sufficient to minimize the infty-norm, which reduces the problem to the well-studied linearly-constrained least squares problem. The continuous version of the problem has the advantage of being easily amenable to parallelization.

In many applications of parallel computing, distribution of the data unambiguously implies distribution of work among processors. But there are exceptions where some tasks can be assigned to one of several processors without altering the total volume of communication. In this paper, we study the problem of exploiting this flexibility in assignment of tasks to improve load balance. We first model the problem in terms of network flow and use combinatorial techniques for its solution. Our parametric search algorithms use maximum flow algorithms for probing on a candidate optimal solution value. We describe two algorithms to solve the assignment problem with \logW_T and vbar P vbar probe calls, w here W_T and vbar P vbar, respectively, denote the total workload and number of proce ssors. We also define augmenting paths and cuts for this problem, and show that anyalgorithm based on augmenting paths can be used to find an optimal solution for the task assignment problem. We then consider acontinuous version of the problem, and formulate it as a linearly constrained optimization problem, i.e., \min\|Ax\|_\infty,\; \rms.t. \; Bx=d. To avoid solving an intractable \infty-norm optimization problem, we show that in this case minimizing the 2-norm is sufficient to minimize the \infty-norm, which reduces the problem to the well-studied linearly-constrained least squares problem. The continuous version of the problem has the advantage of being easily amenable to parallelization. Our experiments with molecular dynamics and overlapped domain decomposition applications proved the effectiveness of our methods with significant improvements in load balance. We also discuss how our techniques can be enhanced for heterogeneous systems.

Strongly connected components of a directed graph can be found in an optimal linear time, by algorithms based on depth first search. Unfortunately, depth first search is difficult to parallelize. We describe two divide--and--conquer algorithms for this problem that have significantly greater potential for parallelization. We show the expected serial runtime of our simpler algorithm to be $O(m\lg n)$, for a graph with $n$vertices and $m$ edges. We then show that the second algorithm has$O(m\lg n)$ worst--case complexity.

On May 10 and 11, 2002, a workshop entitled "Theory and Modeling in Nanoscience" was held in San Francisco, California, sponsored by the offices of Basic Energy Science and Advanced Scientific Computing Research of the Department of Energy. The Basic Energy Sciences Advisory Committee and the Advanced Scientific Computing Advisory Committee convened the workshop to identify challenges and opportunities for theory, modeling, and simulation in nanoscience and nanotechnology, and additionally to investigate the growing and promising role of applied mathematics and computer science in meeting those challenges. This report is the result of those contributions and the discussions at the workshop.