Irregular problems: Difference between revisions
No edit summary |
mNo edit summary |
||
| Line 1: | Line 1: | ||
I am not aware of any satisfactory definition for '''irregular problem''' in the context of parallel computation, though there is a recognizable class of such problems that crop up in diverse application domains including graph analytics, discrete optimization, games, simulation, and visualization. A classic example of an irregular problem is to determine whether or not an undirected graph is connected. We include as computational resources: processing, memory space, and bandwidth. Then, my working definition is this: a computation is irregular to the extent that determining with any accuracy the computational resource requirements as a function of time to solve it as a function of its input requires computational resources comparable to the computational resources required to solve it. A problem is irregular when its most favorable parallel solution is irregular. Put another way, we recognize that a problem is irregular when allocating resources to its solution is far better done dynamically than statically. To determine whether or not a graph is connected can be done trivially sequentially by any graph traversal algorithm such as DFS or BFS; to do so with maximal parallelism, a link-and-compress approach can be used, but is not usually the most work-efficient. There are any number of algorithmic variations along the spectrum. But, there doesn't seem to be any ways to "sample the graph input" so as to determine which algorithm is most efficient; predicting the resources required appears to be as hard as just running the computation. | I am not aware of any satisfactory definition for '''irregular problem''' in the context of parallel computation, though there is a recognizable class of such problems that crop up in diverse application domains including graph analytics, discrete optimization, games, simulation, and visualization. A classic example of an irregular problem is to determine whether or not an undirected graph is connected. We include as computational resources: processing, memory space, and bandwidth. Then, my working definition is this: a computation is irregular to the extent that determining with any accuracy the computational resource requirements as a function of time to solve it as a function of its input requires computational resources comparable to the computational resources required to solve it. A problem is irregular when its most favorable parallel solution is irregular. Put another way, we recognize that a problem is irregular when allocating resources to its solution is far better done dynamically than statically. To determine whether or not a graph is connected can be done trivially sequentially by any graph traversal algorithm such as DFS or BFS; to do so with maximal parallelism, a link-and-compress approach can be used, but is not usually the most work-efficient. There are any number of algorithmic variations along the spectrum. But, there doesn't seem to be any ways to "sample the graph input" so as to determine which algorithm is most efficient; predicting the resources required appears to be as hard as just running the computation. | ||
Given that large irregular problems are important yet have requirements difficult to predict, we are left with a challenge: build a large computing system that can adapt to changing computational demands, utilizing its resources to the extent parallelism is available. The [http://en.wikipedia.org/wiki/Tera_Computer_Company Tera MTA] series of computer system -- now the Cray XMT -- meets this challenge. Based on technology largely developed around 1990, the system is now long-in-the-tooth. [[SoftXMT]] is aimed at revisiting the challenge in the context of today's more advanced technologies. | Given that large irregular problems are important yet have requirements difficult to predict, we are left with a challenge: build a large computing system that can adapt to changing computational demands, utilizing its resources to the extent parallelism is available. The [http://en.wikipedia.org/wiki/Tera_Computer_Company Tera MTA] series of computer system -- now the [http://www.cray.com/products/xmt/ Cray XMT] -- meets this challenge. Based on technology largely developed around 1990, the system is now long-in-the-tooth. [[SoftXMT]] is aimed at revisiting the challenge in the context of today's more advanced technologies. | ||
Revision as of 22:58, 17 September 2010
I am not aware of any satisfactory definition for irregular problem in the context of parallel computation, though there is a recognizable class of such problems that crop up in diverse application domains including graph analytics, discrete optimization, games, simulation, and visualization. A classic example of an irregular problem is to determine whether or not an undirected graph is connected. We include as computational resources: processing, memory space, and bandwidth. Then, my working definition is this: a computation is irregular to the extent that determining with any accuracy the computational resource requirements as a function of time to solve it as a function of its input requires computational resources comparable to the computational resources required to solve it. A problem is irregular when its most favorable parallel solution is irregular. Put another way, we recognize that a problem is irregular when allocating resources to its solution is far better done dynamically than statically. To determine whether or not a graph is connected can be done trivially sequentially by any graph traversal algorithm such as DFS or BFS; to do so with maximal parallelism, a link-and-compress approach can be used, but is not usually the most work-efficient. There are any number of algorithmic variations along the spectrum. But, there doesn't seem to be any ways to "sample the graph input" so as to determine which algorithm is most efficient; predicting the resources required appears to be as hard as just running the computation.
Given that large irregular problems are important yet have requirements difficult to predict, we are left with a challenge: build a large computing system that can adapt to changing computational demands, utilizing its resources to the extent parallelism is available. The Tera MTA series of computer system -- now the Cray XMT -- meets this challenge. Based on technology largely developed around 1990, the system is now long-in-the-tooth. SoftXMT is aimed at revisiting the challenge in the context of today's more advanced technologies.
