Multiple Quadratic Forms: A Case Study in the Design of Data-Parallel Algorithms |
| |
| Affiliation: | 1. Department of Psychiatry, Samsung Medical Center, Sungkyunkwan University School of Medicine, Seoul, South Korea;2. Center for Clinical Research, Samsung Biomedical Research Institute, Seoul, South Korea;3. Yong-In Mental Hospital, Kyunggi-Do, South Korea;4. Dept. of Psychiatry, NHIS Ilsan Hospital, Goyang-si, Gyeonggi-do, Korea;1. Quantum Physics and Magnetism Team, LPMC, Faculty of Science Ben M''sik, Casablanca Hassan II University, Morocco;2. Department of Mathematics, S.P.M. Science and Gilani Arts Commerce College, Ghatanji, Dist. Yavatmal, Maharashtra-445301, India;3. Department of Mathematics, Steve Biko Campus, Durban University of Technology, Durban 4000, South Africa;4. Lab of High Energy Physics, Modeling and Simulations, Faculty of Science, University Mohammed V-Agdal, Rabat, Morocco;1. COHERE, University of Southern Denmark, Department of Business and Economics, Campusvej 55, DK-5500 Odense M, Denmark;2. COHERE, University of Southern Denmark, Institute of Public Health, Department of Business and Economics, Campusvej 55, DK-5500 Odense M, Denmark;1. Institute for Business-to-Busines Marketing, 48143 Münster, Germany;2. Heinz Nixdorf Institute, 33098 Paderborn, Germany |
| |
| Abstract: | Data-parallel implementations of the computationally intensive task of solving multiple quadratic forms (MQFs) have been examined. Coupled and uncoupled parallel methods are investigated, where coupling relates to the degree of interaction among the processors. Also, the impact of partitioning a large MQF problem into smaller non-interacting subtasks is studied. Trade-offs among the implementations for various data-size/machine-size ratios are categorized in terms of complex arithmetic operation counts, communication overhead, and memory storage requirements. Furthermore, the impact on performance of the mode of parallelism used is considered, specifically, SIMD versus MIMD versus SIMD/MIMD mixed-mode. From the complexity analyses, it is shown that none of the algorithms presented in this paper is best for all data-size/machine-size ratios. Thus, to achieve scalability (i.e., good performance as the number of processors available in a machine increases), instead of using a single algorithm, the approach discussed is to have a set of algorithms from which the most appropriate algorithm or combination of algorithms is selected based on the ratio calculated from the scaled machine size. The analytical results have been verified by experiments on the MasPar MP-1 (SIMD), nCUBE 2 (MIMD), and PASM (mixed-mode) prototype. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
