We propose an optimization approach for determining both hardware and software parameters for the efficient implementation of a (family of) applications called dense stencil computations on programmable general purpose computing on graphics processing units. We first introduce a simple, analytical model for the silicon area usage of accelerator architectures and a workload characterization of stencil computations. We combine this characterization with a parametric execution-time model and formulate a mathematical optimization problem that seeks to maximize a common objective function of all the hardware and software parameters. The solution to this problem, therefore, “solves” the codesign problem: simultaneously choosing software-hardware parameters to optimize total performance. We validate this approach by proposing architectural variants of the NVIDIA Maxwell GTX-980 (respectively, Titan X) specifically tuned to a predetermined workload of four common 2-D stencils (Heat, Jacobi, Laplacian, and Gradient) and two 3-D ones (Heat and Laplacian). Our model predicts that performance would potentially improve by 28% (respectively, 33%) with simple tweaks to the hardware parameters, such as tuning the number of streaming multiprocessors, the number of compute cores each contains, and the size of shared memory. We also develop a number of insights about the optimal regions of the design landscape.

Stencil computations are an important class of compute and data intensive programs that occur widely in scientific and engineeringapplications. A number of tools use sophisticated tiling, parallelization, and memory mapping strategies, and generate code that relies on vendor-supplied compilers. This code has a number of parameters, such as tile sizes, that are then tuned via empirical exploration.

We describe a new algorithm for solving the all-pairs shortest-path (APSP) problem for planar graphs and graphs with small separators that exploits the massive on-chip parallelism available in today's Graphics Processing Units (GPUs). Our algorithm, based on the Floyd-War shall algorithm, has near optimal complexity in terms of the total number of operations, while its matrix-based structure is regular enough to allow for efficient parallel implementation on the GPUs. By applying a divide-and-conquer approach, we are able to make use of multi-node GPU clusters, resulting in more than an order of magnitude speedup over the fastest known Dijkstra-based GPU implementation and a two-fold speedup over a parallel Dijkstra-based CPU implementation.

We present a mathematical model and exact algorithm for optimally aligning protein structures using the DALI scoring model. This scoring model is based on comparing the interresidue distance matrices of proteins and is used in the popular DALI software tool, a heuristic method for protein structure alignment. Our model and algorithm extend an integer linear programming approach that has been previously applied for the related, but simpler, contact map overlap problem. To this end, we introduce a novel type of constraint that handles negative score values and relax it in a Lagrangian fashion. The new algorithm, which we call DALIX, is applicable to any distance matrix-based scoring scheme. We also review options that allow to consider fewer pairs of interresidue distances explicitly because their large number hinders the optimization process. Using four known data sets of varying structural similarity, we compute many provably score-optimal DALI alignments. This allowed, for the first time, to evaluate the DALI heuristic in sound mathematical terms. The results indicate that DALI usually computes optimal or close to optimal alignments. However, we detect a subset of small proteins for which DALI fails to generate any significant alignment, although such alignments do exist.

Abstract Bacterium genome plasticity can efficiently be studied by the long‐range polymerase chain reaction (LR‐PCR) technique: genomes of different strains are split into hundreds of short segments which, after LR‐PCR amplification, are used to sketch profiles. The segments have to: (1) cover the entire genome; (2) overlap each other; and (3) be of nearly identical size. This paper addresses the problem of finding a list of segments satisfying these constraints ‘as much as possible’. Two algorithms based on dynamic programming approach are presented. They differ on the optimization criteria for measuring the quality of the covering. The first considers the maximal deviation of the segment lengths relatively to an ideal length. The second automatically finds a segment length that minimizes the maximal deviation. Copyright © 2005 John Wiley & Sons, Ltd.

Summary form only given. Bacterium genome plasticity can efficiently be studied by long-range PCR: genomes of different strains are split into hundreds of short segments which, after LR-PCR amplification, are used to sketch profiles. The segments have : (1) to cover the entire genome, (2) to overlap each other, and (3) to be of nearly identical size. We address the problem of finding a list of segments satisfying these constraints "as much as possible". Two algorithms based on dynamic programming approach are presented. They differ on the optimization criteria for measuring the quality of the covering. The first one considers the maximal deviation of the segment lengths relatively to an ideal length. The second one automatically finds a segment length which minimizes the maximal deviation.

Abstract For the Protein Threading Problem (PTP) we propose a network‐flow like formulation. We also show its equivalence with a generalization of the shortest path problem on a graph with a very particular structure. The underlying Mixed Integer Programming (MIP) model proves to be very appropriate for the PTP—large real‐life instances have been solved much faster by using only the MIP solver CPLEX instead of a known special‐purpose branch and bound algorithm. The properties of the MIP model permit a decomposition of the main problem into a large number of subproblems (tasks). We show that a branch and cut strategy can be efficiently applied for solving these tasks in a parallel manner, which leads to a significant reduction in the total running time. Computational experiments with large problem instances are presented. Copyright © 2004 John Wiley & Sons, Ltd.

This paper presents a new network-flow formulation for the problem of predicting 3D protein structures using threading. Several integer-programming models based on this formulation are proposed and compared. These models allow for an efficient decomposition and for the application of a parallel branch-and-cut algorithm, significantly reducing the running time. The efficiency of our approach has been confirmed by extensive computational experiments.

For 2D iteration space tiling, we address the problem of determining the tile parameters that minimize the total execution time on a parallel machine. We consider uniform dependency computations tiled so that (at least) one of the tile boundaries is parallel to the domain boundaries. We determine the optimal tile size as a closed form solution. In addition, we determine the optimal number of processors and also the optimal slope of the oblique tile boundary. Our results are based on the BSP model, which assures the portability of the results. Our predictions are justified on a sequence global alignment problem specialized to similar sequences using Fickett's k-band algorithm, for which our optimal semi-oblique tiling yields an improvement of a factor of 2.5 over orthogonal tiling. Our optimal solution requires a block-cyclic distribution of tiles to processors. The best one can obtain with only block distribution (as many authors require) is three times slower. Furthermore, our best running time is within 10 percent of the "predicted theoretical peak" performance of the machine!.

Dynamic programming is an important combinatorial optimization technique that has been widely used in various fields such as control theory, operations research, computational biology and computer science. Many authors have described parallel dynamic programming algorithms for the family of multistage problems. More scarce is the literature for the more general class of problems where dependences appear between non-consecutive stages. Among the important problems falling in this class is the RNA base pairing problem. In this study we propose a new parallel scheme for a large class of recurrences with triangular iteration space and nonuniform dependences that includes the RNA base pairing problem. We derive two different instances of this scheme that correspond to an horizontal and a vertical traverse of the iteration domain. We develop and extend the tiling approach for this particular class. We formulate and analytically solve the optimization problem determining the tile size that minimizes the total execution time of the tiled program on a distributed memory parallel machine. Our analyze is based on the BSP model, which assures the portability of the obtained results. The computational experiments carried out on the CRAY T3E behave according to the predictions of our theoretical model.

For 2-D iteration space tiling, we address the problem of determining the tile parameters that minimize the total execution time under the BSP model. We consider uniform dependency computations, tiled so that (at least) one of the tile boundaries is parallel to the domain boundary. We determine the optimal tile size as a closed form solution. In addition, we determine the optimal number of processors and also the optimal slope of the oblique tile boundary.

We discuss in this paper the problem of finding the optimal tiling transformation of three-dimensional uniform recurrences on a two-dimensional torus/grid of distributed-memory general-purpose machines. We show that even for the simplest case of recurrences which allows for such transformation, the corresponding problem of minimizing the total running time is a non-trivial non-linear integer programming problem. For the later we derive an O(1) algorithm for finding a good approximation solution. The theoretical evaluations and the experimental results show that the obtained solution approximates the original minimum sufficiently well in the context of the considered problem. Such analytical results are of obvious interest and can be successfully used in parallelizing compilers as well as in performance tuning of parallel codes.

We present a parallel solution to the unbounded knapsack problem on a linear systolic array. It achieves optimal speedup for this well-known, NP-hard problem on a model of computation that is weaker than the PRAM. Our array is correct by construction, as it is formally derived by transforming a recurrence equation specifying the algorithm. This recurrence has dynamic dependencies, a property that puts it beyond the scope of previous methods for automatic systolic synthesis. Our derivation thus serves as a case study. We generalize the technique and propose a systematic method for deriving systolic arrays by nonlinear transformations of recurrences. We give sufficient conditions that the transformations must satisfy, thus extending systolic synthesis methods. We address a number of pragmatic considerations: implementing the array on only a fixed number of PEs, simplifying the control to just two counters and a few latches, and loading the coefficients so that successive problems can be pipelined without any loss of throughput. Using a register level model of VLSI, we formulate a nonlinear optimization problem to minimize the expected running time of the array. The analytical solution of this problem allows us to choose the memory size of each PE in an optimal manner.

In pipelined parallel computations the inner loops are often implemented in a block fashion. In such programs, an important compiler optimization involves the need to statically determine the grain size. This paper presents extensions and experimental validation of the previous results of Andonov and Rajopadhye (1994) on optimal grain size determination.

We systematically derive an improved algorithm (called the sparse algorithm) for the general knapsack problem which has better average case performance than the standard (dense) dynamic programming algorithm. The derivation is based on transformation of the standard recurrences into stream functional programs, and cannot be achieved by the usual space-time mapping techniques because the dependencies are statically unpredictable. Furthermore such a sparse algorithm for the general knapsack problem has not been proposed in the literature, to the best of our knowledge. We also implement the sparse algorithm on a linear asynchronous array with constant size memory on each PE (i.e., a wavefront array processor). Using LPGS partitioning, the algorithm can run on an arbitrary size ring and has optimal time speedup.>

The authors first present a formal derivation and proof of correctness of a systolic array for the knapsack problem, an NP-complete problem whose dependency graph is not completely known statically. With q PEs, each with a fixed size memory, the arraystretch runs in /spl Gamma/(mc/q), which gives optimal speedup of the algorithm. However, it has an intricate tag-based control mechanism which is difficult to implement, and the authors improve the architecture so that the control can be implemented with two simple counters and a few flip-flops. Cofficient loading is done with a multi-rate clock which avoids the need for shadow registers. The authors then explore the tradeoff between the number of PEs and memory size, /spl alpha/, using the expected running time of the algorithm as a cost measure and a register level model of VLSI. It is shown analytically how /spl alpha/ may be chosen to optimize the total computation time, yielding an area time optimal circuit.>

The authors propose a modular 2-D torus pipelined processing elements for solving the general knapsack problem of arbitrary size. Each cell has a fixed storage capacity alpha /sub 0/ independent of the particular knapsack problem to be solved. They study the vertical speed up defined as the speed up achieved upon the I-D torus, when the capacity of the knapsack goes to infinity; and its associated efficiency. The knapsack problem is a very important optimization problem because it has a wide range of applications and also appears as a suboptimization task of other optimization schemes. Its dependence graph lacks the regularity usually required for systolic implementation. Its shape namely depends on the set of weights to be included in the knapsack. Therefore the distribution of weights influences the speed up. Precisely they show that the minimum and maximum weights w/sub min/ and w/sub max/ define an upper bound for the possible vertical speed up: w/sub max//(w/sub max/-w/sub min/+2). alpha /sub 0/ is also an upper bound of this speed up. They simulate a cell with a larger memory grouping cells g by g, where g=(w/sub max// alpha /sub 0/). The torus always reaches a quarter of its upper bound with an efficiency of 1/(4*g).>