Search

It is shown that Cartesian product (CP) graph-based network methods provide a useful framework for the design of reliable parallel computer systems. Given component networks with prespecified connectivity, more complex networks with known connectivity and terminal reliability can be developed. CP networks provide systematic techniques for developing reliable fault-tolerant routing schemes, even for very complex topological structures. The authors establish the theoretical foundations that relate the connectivity of a CP network, the connectivity of the component networks, and the number of faulty components: present an adaptive generic algorithm that can perform successful point-to-point routing in the presence of faults: synthesize, using the theoretical results, this adaptive fault-tolerant algorithm from algorithms written for the component networks: prove the correctness of the algorithm: and show that the algorithm ensures following an optimal path, in the presence of many faults, with high probability. >

High-performance computing, or supercomputing, is the field of exploiting massive parallelism through advanced hardware technology and architectures to solve large application problems. There have been many important turning points at which the field has made significant shifts and changes. Among these are the golden years of vector supercomputers, the rapid developments of the massively parallel architectures in the late 1980s and early 1990s, the cluster computing era starting from the mid 1990s, the Grid Computing, from the late 1990s, the development of the Earth Simulator in Japan, the U.S. regaining of the leadership of Supercomputing with the introduction the IBM Blue Gene L, then finally the emergence of the first PetaFLOPS machine, the roadrunner, in mid 2008. This talk will consider the progress in this field from an architectural, performance and historical points of view. It will then introduce some of the implications and challenges associated with the latest developments and the needed research directions. It will then introduce some of the ongoing efforts that are likely to produce the next generation of Parallel Supercomputers, such as the DARPA High-Productivity Computing Systems initiative.

The Partitioned Global Address Space (PGAS) programming paradigm offers ease-of-use in expressing parallelism through a global shared address space while emphasizing performance by providing locality awareness through the partitioning of this address space. Therefore, the interest in PGAS programming languages is growing and many new languages have emerged and are becoming ubiquitously available on nearly all modern parallel architectures. Recently, new parallel machines with multiple cores are designed for targeting high performance applications. Most of the efforts have gone into benchmarking but there are a few examples of real high performance applications running on multicore machines. In this paper, we present and evaluate a parallelization technique for implementing a local DNA sequence alignment algorithm using a PGAS based language, UPC (Unified Parallel C) on a chip multithreading architecture, the UltraSPARC T1., {"references":["El-Ghazawi T., Carlson W., Sterling T, Yelick K.: UPC: Distributed\nShared Memory Programming. Book, John Wiley and Sons Inc.,\nNewYork. ISBN: 0-471-22048-5, 2005.","Yap T. K., FriederO., Martino R. L.: Parallel Computation in Biological\nSequence Analysis. IEEE Transactions on Parallel and Distributed\nSystems, Vol. 9, N 3, pp. 283-294, 1998.","Needleman, S. B., Wunsch C. D: A general method applicable to the\nsearch for similarities in the amino acid sequence of two proteins. Journal\nof Molecular Biology, Vol. 47, pp. 443-453, 1970.","Smith W., Waterman M.: Identification of Common Molecular Subsequences.\nJournal of Molecular Biology Vol. 147, pp. 195-197, 1981.","Gaber J.: Complexity Measure Approach for Partitioned Shared Memory\nModel, Application to UPC. Research report RR-10-04. Universite de\nTechnologie de Belfort-Montbeliard, 2004.","Lu M., Lin L.: Parallel algorithms for the Longest Common Subsequence\nProblem. IEEE Transaction on Parallel and Distributed System, Vol.5,\npp.835-848, 1994.","Valiant L.G.: A bridging model for parallel computation. Communication\nof the ACM, Vol. 33, N 8, pp. 103-111, 1990.","http://www.sun.com/servers/coolthreads/t1000/benchmarks.jsp","Garcia T., Myoupo J-F., Seme D.: A Coarse-Grained Multi-computer\nalgorithm for the longest common subsequence problem. 11-th Euromicro\nConference on Parallel Distributed and Network based Processing, 2003.\n[10] Alves C. E. R., Cceres E. N., Dehne F.: Parallel Dynamic Programming\nfor Solving the String Editing Problem on a CGM/BSP. In proceeding of\nACM SPAA-02, pp. 275-281, 2002.\n[11] Alves C. E. R. Cceres E. N., Dehne F. , Song S. W.: A Parallel Wavefront\nAlgorithm for Efficient Biological Sequence Comparison. International\nConference on Computational Science and its Applications, Montreal,\nCanada, May 18-21, Lecture Notes in Computer Science, V. 2668, pp.\n249-258, 2003.\n[12] Nicholas P. P.: Searching Biological Sequence Databases Using Distributed\nAdaptive Computing. Master thesis, Master of Science in Computer\nEngineering, Virginia Polytechnic Institute and State University,\n2003, available at http://scholar.lib.vt.edu/theses/\n[13] Chen Y., Wan A., Liu W.: A fast Parallel Algorithm for Finding\nthe Longest Common Sequence of Multiple Bio-sequences. Symposium\nof Computations in Bioinformatics and Bioscience (SCBB06). In conjunction\nwith the International Multi-Symposiums on Computer and\nComputational Sciences 2006 (IMSCCS06), 2006.\n[14] Bader D.A., Madduri K.,: A Graph-Theoretic Analysis of the Human\nProtein-Interaction Network Using Multicore Parallel Algorithms. Sixth\nIEEE International Workshop on High Performance Computational Biology\n(HiCOMB-07), 2007.\n[15] Bader D. A., Kanade V., Madduri K.: SWARM, A Parallel Programming\nFramework for Multicore Processors. First Workshop on Multithreaded\nArchitectures and Applications (MTAAP-07), 2007.\n[16] Voss G., Schrder A., Mller-Wittig W. Schmidt B.: Biological\nSequence Alignment on Graphics Processing Units. Available at\nhttp://www.ntu.edu.sg/home/asbschmidt/paper/BioGPU.pdf\n[17] Kayi A., Yao Y., El-Ghazawi T., Newby G.: Experimental Evaluation\nofEmerging Multi-core Architectures, Workshop on Performance\nModeling, Evaluation, and Optimisation of Ubiquitous Computing and\nNetworked Systems (PMEO07) IPDPS07 Proceedings, pp. 1-6, 2007.\n[18] Chen W-Y., Bonachea D., Duell J., Husbands P., Iancu C., Yelick K.:\nA Perfor- mance Analysis of the Berkley UPC Compiler. In Annual\nInternational Conference on Supercomputing (ICS), 2003.\n[19] Cantonnet F., El Ghazawi T., Lorenz P., Gaber J.: Fast Address Translation\nTech- niques for Distributed Shared Memory Compilers. International\nParallel and Dis- tributed Processing Symposium IPDPS06, 2006.\n[20] Bakhouya M., Gaber J., El-Ghazawi T.: Towards a Complexity Model\nfor Design and Analysis of PGAS-Based Algorithms, HPCC 2007 Proceedings,\nLNCS 4782 Springer, ISBN 978-3-540-75443-5, pp.672-682,\n2007."]}

Reconfigurable computers (RCs) are those parallel systems that are designed around multiple general-purpose processors and multiple field programmable gate array (FPGA) chips. These systems can leverage the synergism between conventional processors and FPGAs to provide low-level hardware functionality at the same level of programmability as general-purpose computers. RCs have proposed very high processing capabilities for computationally intensive applications such as Image Processing. This is due to the inherently parallel operation paradigm of the FPGA hardware. In this paper we present the design and implementation of image processing kernels for RCs. This library of kernels have been tested and verified for performance on one of the state-of-the-art reconfigurable computers, SRC-6E. This paper shows that RCs are between 8 to 400 times faster than comparable Pentiums for image based tasks.

A theoretical study of the connectivity and fault tolerance of Cartesian product networks is presented. The theoretical results are used to synthesize provably correct adaptive fault-tolerant algorithms from ones written for the component networks. The theoretical foundations that relate the connectivity of a Cartesian product network, the connectivity of the component networks, and the number of faulty components are established. It is shown that the connectivity of a product network is at least the sum of the connectivities of its factor networks. Based on the constructive connectivity proof, an adaptive, generic, distributed algorithm that can perform successful point-to-point routing in product networks, in the presence of faults, is devised. A proof of correctness of the algorithm is provided. >

The Tropical Rainfall Measuring Mission (TRMM) satellite was launched with the first space-borne Precipitation Radar (PR) to collect accurate precipitation measurements. To validate the space data set, well-instrumented and calibrated ground validation (GV) sites are established. The paper is a first attempt to merging rainfall estimates from space-borne and ground based radars. We describe a technique to forecast bogus PR data that occurred before and after the passage of the PR over a GV site. Several simulations are performed at 10-minute intervals of GV reflectivity data at Melbourne, Florida on March 9, 1998 from 8:00 am to 9:00 am to track continuously PR reflectivity which overpass the GV site at 8:30 am. We apply genetic algorithms (GAs) to find the needed transformations to produce a time series of PR reflectivity data. The transformations include translation and rotation. By registering the PR original data following the transformed results, the new PR data are presented 20 minutes before and after the overpass. Finally, the statistic analyses are used to compare the relationship between these different sources of reflectivity. The increased correlation between GV and bogus PR reflectivity data demonstrated the potential use of GAs in merging multi-platform remote sensing data.

In remote sensing, image registration is to find the best transform between a reference and input images that may be different due to changes in position or altitude of or noise in the sensors. Image registration is one of the first steps in the analysis of remotely sensed images and requires high computational resources. The computation time is affected by two factors: search data size and search space. This paper describes an efficient image registration algorithm that uses multi-resolution wavelet decomposed images to reduce the search data size, and Genetic Algorithms to optimize the search solution space. Experimental results have shown subpixel accuracy and high efficiency over conventional methods.