Computations on two-dimensional arrays such as matrices and images are one of the most fundamental and ubiquitous things in computational science and its vast application areas, but development of efficient parallel p...
详细信息
Computations on two-dimensional arrays such as matrices and images are one of the most fundamental and ubiquitous things in computational science and its vast application areas, but development of efficient parallel programs on two-dimensional arrays is known to be hard. In this paper, we propose a compositional framework that supports users, even with little knowledge about parallel machines, to develop both correct and efficient parallel programs on dense two-dimensional arrays systematically. The key feature of our framework is a novel use of the abide-tree representation of two-dimensional arrays. The presentation not only inherits the advantages of tree representations of matrices where recursive blocked algorithms can be defined to achieve better performance, but also supports transformational development of parallel programs and architecture-independent implementation owing to its solid theoretical foundation - the theory of constructive algorithmics.
Trees are important datatypes that are often used in representing structured data such as XML. Though trees are widely used in sequential programming, it is hard to write efficient parallel programs manipulating trees...
详细信息
Trees are important datatypes that are often used in representing structured data such as XML. Though trees are widely used in sequential programming, it is hard to write efficient parallel programs manipulating trees, because of their irregular and ill-balanced structures. In this paper, we propose a solution based on the skeletal approach. We formalize a set of skeletons (abstracted computational patterns) for rose trees (general trees of arbitrary shapes) based on the theory of constructive algorithmics. Our skeletons for rose trees are extensions of those proposed for lists and binary trees. We show that we can implement the skeletons efficiently in parallel, by combining the parallel binary-tree skeletons for which efficient parallel implementations are already known. As far as we are aware, we are the first who have formalized and implemented a set of simple but expressive parallel skeletons for rose trees. (c) 2006 Elsevier B.V. All rights reserved.
The accumulation strategy consists of generalizing a function over an algebraic data structure by inclusion of an extra parameter, an accumulating parameter, for reusing and propagating intermediate results. However, ...
详细信息
The accumulation strategy consists of generalizing a function over an algebraic data structure by inclusion of an extra parameter, an accumulating parameter, for reusing and propagating intermediate results. However, there remain two major difficulties in this accumulation strategy. One is to determine where and when to generalize the original function. The other, surprisingly not yet receiving its worthy consideration, is how to manipulate accumulations. To overcome these difficulties, we propose to formulate accumulations as higher order catamorphisms, and provide several general transformation rules for calculating accumulations (i.e., finding and manipulating accumulations) by calculation-based (rather than a search-based) program transformation methods. Some examples are given for illustration.
暂无评论