Sparse LU decomposition is the core computation in the direct method that solves sparse systems of linear equations. Only little work has been conducted on parallelizing it on FPGAs. In this paper, we study parallelization strategies for sparse LU decomposition on FPGAs. We first analyze how to parallelize the right-looking algorithm and find that this algorithm is not suitable for FPGAs. Then the left-looking algorithm is analyzed and considered as better candidate than the right-looking version. Our design derived from the left-looking algorithm is based on a simple yet efficient parallel computational model for FPGAs. Our design mainly consists of multiple parallel processing elements (PEs). A total of 14 PEs can be integrated into a Xilinx Virtex-5 XC5VLX330. Unlike related work, where their designs are applied to sparse matrices from particular application domains, our hardware design can be applied to any symmetric positive definite or diagonally dominant matrices.

LU decomposition for dense matrices is an important linear algebra kernel that is widely used in both scientific and engineering applications. To efficiently perform large matrix LU decomposition on FPGAs with limited local memory, a block LU decomposition algorithm on FPGAs applicable to arbitrary matrix size is proposed. Our algorithm applies a series of transformations, including loop blocking and space-time mapping, onto sequential nonblocking LU decomposition. We also introduce a high performance and memory efficient hardware architecture, which mainly consists of a linear array of processing elements (PEs), to implement our block LU decomposition algorithm. Our design can achieve optimum performance under various hardware resource constraints. Furthermore, our algorithm and design can be easily extended to the multi-FPGA platform by using a block-cyclic data distribution and inter-FPGA communication scheme. A total of 36 PEs can be integrated into a Xilinx Virtex-5 XC5VLX330 FPGA on our self-designed PCI-Express card, reaching a sustained performance of 8.50 GFLOPS at 133 MHz for a matrix size of 16,384, which outperforms several general-purpose processors. For a Xilinx Virtex-6 XC6VLX760, a newer FPGA, we predict that a total of 180 PEs can be integrated, reaching 70.66 GFLOPS at 200 MHz. Compared to the previous work, our design can integrate twice the number of PEs into the same FPGA and has significantly higher performance.

In performance modeling of parallel synchronous iterative applications, the longest individual execution time among parallel processors determines the iteration time and often must be estimated for performance analysis. This involves the mean maximum calculation which has been a challenge in computer modeling for a long time. For large systems, numerical methods are not suitable because of heavy computation requirements and inaccuracy caused by rounding. On the other hand, previous approximation methods face challenges of accuracy and generality, especially for heterogeneous computing environments. This paper presents an interesting property of extreme values to enable Effective Mean Maximum Approximation (EMMA). Compared to previous mean maximum execution time approximation methods, this method is more accurate and general to different computational environments.

This paper proposes a high performance least square solver on FPGAs using the Cholesky decomposition method. Our design can be realized by iteratively adopting a single triangular linear equation solver for modified Cholesky decomposition and forward/backward substitutions. Good performance is achieved by optimizing the Cholesky factorization algorithms, reordering the computation and thus alleviating the data dependency. Dedicated hardware architecture for solving triangular linear equations is designed and implemented for different precision requirements. Compared to software on a Pentium 4, our design achieves a significant speedup.

This paper studies the issue of human resource plan in an employee leasing center. The center is engaged in the business of leasing its own contract employees and acting as an agent for flexible employees outside the center. The employees considered in this paper belong to one type of employees that are high-ranked and important for the firms. But this type of employees can be classified into two parts: the contract employees in the employee leasing center and the temporary employees in the manpower market. At first we take into account recruitment/dismissal factors and propose stochastically optimal multi-period decision model of the problem. In the model there are stochastic constraint conditions and the decision (control) in each period is the number of the contract employees that are recruited or dismissed by the center and the objective is to maximize the overall expected net revenue of the center over planning horizon. Then we transform the stochastic optimal control problem into the determined optimal control problem by transforming stochastic constraint conditions into determined constraint conditions. Furthermore we analyze the limits of the states in each period, develop a dynamic programming algorithm to search for an optimal solution to the problem and a heuristic approximate algorithm to find out an approximate optimal solution. Analyzing reveals that the heuristic algorithm is superior to the dynamic programming in time complexity. Finally, we use two algorithms to solve some simulating data case. The results reveal that the error between the two solutions is no more than 5% for each case.

Compared to higher-precision data formats, lower-precision data formats result in higher performance for computational intensive applications on FPGAs because of their lower resource cost, reduced memory bandwidth requirements, and higher circuit frequency. On the other hand, scientific computations usually demand highly accurate solutions. This paper seeks to utilize lower-precision data formats whenever possible for higher performance without losing the accuracy of higher-precision data formats by using mixed-precision algorithms and architectures. First, we analyze the floating-point performance of different data formats on FPGAs. Second, we introduce mixed-precision iterative refinement algorithms for linear solvers and give error analysis. Finally, we propose an innovative architecture for a mixed-precision direct solver for reconfigurable computing. Our results show that our mixed-precision algorithm and architecture significantly improve the performance of linear solvers on FPGAs.

Creating a high throughput sparse matrix vector multiplication (SpMxV) implementation depends on a balanced system design. In this paper, we introduce the innovative SpMxV solver designed for FPGAs (SSF). Besides high computational throughput, system performance is optimized by reducing initialization time and overheads, minimizing and overlapping I/O operations, and increasing scalability. SSF accepts any matrix size and can be easily adapted to different data formats. SSF minimizes the control logic by taking advantage of the data flow via an innovative accumulation circuit which uses pipelined floating point adders. Compared to optimized software codes on a Pentium 4 microprocessor, our design achieves up to 20x speedup.

In the operations of the container terminals, berth scheduling problem is one of the main bottlenecks that restrict the container terminals to reduce the turnaround time of the ships and the operation costs. In this paper we described a nonlinear model for the berth scheduling problem and solved this model by the genetic algorithm GA and the hybrid optimization strategy GASA (namely the combination of genetic algorithm and simulated annealing) respectively. The results indicated that compared with GA, the GASA algorithm increased the diversity of the individuals, accelerated the evolution process and avoided sinking into the local optimal solution early