# Alexandros Gerbessiotis

About Me

Graduate Level Courses

- CS 667: Design Techniques for Algorithms. Fall 2006, Fall 2007.
- CS 610: Data Structures and Algorithms. Spring 2007, Spring 2008, Fall 2008.

Advanced Undergraduate Courses

- CS 435: Advanced Data Structures and Algorithm Design. Fall 2006, Spring 2007, Fall 2007, Spring 2008, Fall 2008.

Research Interests

Architecture independent parallel algorithm design and implementation, high productivity/performance cluster computing, models of parallel computation, Bulk-synchronous parallel computing, interprocessor communication network performance assessment, experimental algorithmics, graph theory and combinatorics.

Current Projects

**PowerGrid Project**Cluster-based implementations of power-flow analysis and contingency analysis algorithms and benchmarking for the development of FPGA-based bulk-synchronous parallel algorithms. This is joint work with Prof. S. Ziavras at the ECE Department at NJIT (NJIT group) and Drexel University.**Research supported by a Department of Energy (DOE) grant****High Performance and Productivity Computing Systems for space weather research**. This is joint work with colleagues in the Physics Department at NJIT (the space weather part) and the CS Department (the image processing part).**Research is supported by NSF ITR grant (Sep 1, 2003- Aug 31, 2007) IIS-0324816 in which i serve as a Co-Principal Investigator**.**Parallel Algorithms in Finance**Design and implement parallel algorithms for finance-based problems such as option price valuations on binomial and trinomial trees either directly or using finite difference methods (explicit and implicit). Design algorithms in an architecture independent way and suited for high-latency systems such as PC clusters.**This research was partially supported by NSF/MRI grant NSF EIA-9977508 that run from Sep 1, 1999 through Aug 31, 2003, in which i served as a Co-Principal Investigator**.**Latency Tolerant algorithms for matrix computations**Design and implement latency tolerant algorithms for dense and sparse matrix computations and FFT problems.**This was also partially supported by NSF/MRI grant NSF EIA-9977508.****Internal and External Memory Sorting**Design, analyze and examine parallel performance of deterministic and randomized sorting algorithms on cluster of SMP workstations.**Parallel Algorithms for Proximity Searching in large texts and GIS systems.**Joint work with M. Marin (U. de Magallanes, Chile).

Research Results

In the past three years I have been involved in architecture independent design, analysis and implementation of parallel algorithms on a cluster of PC workstations that has been set up at the CS Department at NJIT under the support of NFS under Grant MRI NSF EIA-9977508 and SBR grant 421350.

Information about the PC cluster lab, research results obtained, and publically available source code can be obtained through the links below.

- PC Cluster Laboratory (CS Department) The laboratory was established with support from NSF MRI EIA-9977508 Grant and matching funds from NJIT, as well as support from grant SBR 421350. This link is under construction and updated frequently.
- General Software Code that is being used in published or submitted papers.
- Parallel Software Code Building
**architecture independent**and**parallel library independent**parallel code. The introduced algorithms are designed and analyzed in an architecture independent way under the Bulk-Synchronous Parallel (BSP) model of computation. In order to support and verify the theoretical results we implement many of the parallel algorithms using various communication libraries. The parallel codes we have been developing can be run under LAMMPI and BSPlib. Only recompilation of the same source is required for our code to run on one or the other library. This**communication library portability**comes at no significant cost as attested by the comparable and high performance of the implemented algorithms. - Recent Publications

Works in Progress

- A. V. Gerbessiotis.
*``A parallelism-motivated sequential sorting framework´´*, August 2008. Source code is also available separately through the research*link*of this webpage.*Available in Postscript(274K).**Available in PDF(184K).* - S.M. Iyear, M.K. Nakayama, and A. V. Gerbessiotis.
*``A Markovian Dependability Model with Cascading Failures´´*.*Available in Postscript (1407k).* - A. V. Gerbessiotis.
*``Parallel option price valuations with the explicit finite difference method´´*, 2008. Source code is also available separately through the research*link*of this webpage.*Available in PDF.* - A. V. Gerbessiotis, C. J. Siniolakis.
*``A new randomized sorting algorithm on the BSP model ´´*.*Available in Compressed/Postscript (205k).* - A. V. Gerbessiotis, C. J. Siniolakis.
*``BSP Sorting: An experimental Study ´´*, Submitted for journal publication.

Journals

- S.G. Ziavras, A. V. Gerbessiotis, and R. Bafna.
*``Coprocessor design to support MPI primitives in configurable multiprocessors. ´´*, Integration - the VLSI Journal, Vol. 40, No.3, pp. 235-252, 2007, Elsevier. - A. V. Gerbessiotis, C. J. Siniolakis.
*``A probabilistic analysis of the Floyd-Rivest expected time selection algorithm´´*. International Journal of Computer Mathematics, Vol 82, Number 5, May 2005, Taylor & Francis Publishers. An early manuscript circa 2002 is available in*in Postscript.* - A. V. Gerbessiotis, S. Y. Lee.
*``Remote memory access : A case for portable, efficient and library independent parallel programming´´*, Scientific Programming, Vol 12., Number 3, 2004, pp. 169-184. A preliminary version is available*here (in .ps),*and a more-up-to-date*there (in .ps).*Source code of the experimental portion is available at the Cluster link of the homepage under Software:*communication performance assessment benchmarks,**matrix multiplication benchmarks,**radix-sort benchmarks.*The preliminary version is available as Techninal report CS-03-12*in Postscript.* - A. V. Gerbessiotis.
*``An Architecture Independent Study of Parallel Segment Trees´´*, To appear in Journal of Discrete Algorithms, 2005. A very early preliminary version of this paper is*available in Compressed/Postscript (162k).* - A. V. Gerbessiotis, C. J. Siniolakis.
*``Probabilistic Integer Sorting´´*, Information Processing Letters, 90(4), pp. 187-193, 2004, Elsevier B.V. An early manuscript is available in*in Compressed Postscript(135K).*Source code related to the journal version of the paper is also available through the research link of this webpage. - A. V. Gerbessiotis.
*``Trinomial-tree based parallel option price valuations´´*, Parallel Algorithms and Applications, Vol 18, Number 3, December 2003, pp. 181-196. A presubmission version is available as Technical Report CS-02-03*cs0203.ps.gz (162k).*Source code is also available separately through the research link of this webpage. - A. V. Gerbessiotis.
*``Architecture independent parallel binomial tree option price valuations´´*, Parallel Computing journal, 30:2(2004), pages 303-318, Elsevier Science, BV. A presubmission version is available as Technical Report CS-02-02*cs0202.ps.gz (160k).*Source code is also available separately through the research link of this webpage. - A. V. Gerbessiotis, C. J. Siniolakis.
*``Randomized selection in n+C+o(n) comparisons´´*, Information Processing Letters, 88(3), pp. 95-100, 2003. An early manuscript (presubmission version) is*available in Compressed/Postscript (126k)*. - A. V. Gerbessiotis, C. J. Siniolakis.
*``Increasing the efficiency of existing sorting algorithms by using randomized wrappers´´*, The Computer Journal, Vol 46(5), pp 498-504, 2003. An earlier presubmission version is*available in Compressed/Postscript (205k).* - A. V. Gerbessiotis.
*``Random Graphs in A Neural Computation Model´´*, Internation Journal of Computer Mathematics, Vol 80, June 2003, pp. 689-707. An earlier version is available at*Available in Postscript (400k).* - A.V.Gerbessiotis and C.J.Siniolakis.
*`` Architecture Independent Parallel Selection with Applications to Parallel Priority Queues´´.*Theoretical Computer Science, 301/1-3, pp. 119-142, 2003. - A. V. Gerbessiotis, C. J. Siniolakis, and A. Tiskin.
*``Parallel Priority Queue and List Contraction: The BSP Approach´´.*Computing and Informatics, Vol. 21, 2002, 1-32. - A. V. Gerbessiotis, C. J. Siniolakis.
*``Merging on the BSP Model´´*, Parallel Computing, 27 (2001), page 809-822, Elsevier Science, BV. An earlier version is available*Available in Compressed/Postscript (99k)* - A. V. Gerbessiotis.
*``Architecture Independent Parallel Algorithm Design: Theory vs Practice´´,*Future Generation Computer Systems, 18(2002), 573-593, Elsevier Science B.V. - A.V.Gerbessiotis and C.J.Siniolakis.
*``Efficient Deterministic Sorting on the BSP Model´´.*Parallel Processing Letters, Vol 9, no 1 (1999), pp 69-79, World Scientific Publishing Company. - A.V.Gerbessiotis and C.J.Siniolakis.
*``Ordered h-Level Graphs on the BSP Model´´.*In special issue, Journal of Parallel and Distributed Computing, 49, pages 98-110, Academic Press, 1998. - A.V. Gerbessiotis.
*``Practical Considerations of Parallel Simulations and Architecture Independent Parallel Algorithm Design´´.*In Journal of Parallel and Distributed Computing, 53, Academic Press, 1998. - A.V. Gerbessiotis.
*``A Graph-theoretic Result for a Model of Neural Computation´´.*Discrete Applied Mathematics 82(1998), pp 257-262. Elsevier Science B.V, 1998. - A.V.Gerbessiotis.
*``Close-to-Optimal and Near-Optimal Broadcasting in Random Graphs´´.*Discrete Applied Mathematics 63(1995), pp 129-150. Elsevier Science B.V., 1995. - A.V.Gerbessiotis.
*``Broadcasting in Random Graphs´´.*Discrete Applied Mathematics, 53(1994), pp 149-170. Elsevier Science B.V., 1994. - A.V. Gerbessiotis and L.G.Valiant.
*``Direct Bulk-Synchronous Parallel Algorithms´´.*Journal of Parallel and Distributed Computing, Vol. 22, pp 251-267. Academic Press, 1994.