Software Exchange, Class Material

and Templates for

Parallel Computing

(http://www.netlib.org/nse/)

Jack Dongarra - U Tennessee and ORNL

(http://www.netlib.org/utk/people/JackDongarra.html)

Sharing of Software and Information Among Members of the High Performance Computing and Communications (HPCC) community.

Overview

• Motivation

• National High-Performance Software Exchange
• Material on Computational Science Education
• Templates for Linear Algebra

Goals:

• To facilitate an active exchange program for HPCC software and enabling technologies via the National Information Infrastructure.
  

• To promote contributions and use by Grand Challenge teams, as well as other members of the high performance computing community.
  

Software here includes algorithms, specifications, designs, documentations, reports...

NHSE Components

• Outreach and technology transition
  • To the HPCC user community and industry
• Distribution via the WWW
• Discipline oriented repository
• Uniform user interface
• Multilevel software review system
  • Unreviewed
  • Partially reviewed
  • Reviewed
• Measurement
• Hypertext road map
• Publishing tools
  • Repository-in-a-box
• Naming & authentication architecture
• Selective capitalization of emerging technologies

=9.in ../NSE-PTOOLS/virt_repo.idraw

Intended Audience

• HPCC application and computer science community
  • Source of material for NHSE

• Users of NASA, NSF, DOE and other supercomputer centers
  • Good targets for NHSE
  • Natural support organization: supercomputer center staff
• Other users of high performance computers
  • Current and potential industrial users
  • No natural support organization
• Applicable to other domains

NHSE Prototype

• Based on Existing Technologies
  • WWW Browser (Mosaic / Netscape / etc)
    • Distributed
    • Scalable
    • URL: http://www.netlib.org/nse/

  • Netlib
    • Repository for math software since 1985

• Repositories Currently Available
  • Netlib, Softlib, CITlib
  • ASSET - (Asset Source for SW Engineering Tech.)
  • CARDS - (Comprehensive Approach to
    Reusable Defense SW)
  • ELSA - (Electronic Library Services and Appl.)
  • GAMS (Virtual Software Repository)
  • STARS - (SW Technology for Adaptable,
    Reliable Systems)
  • Many examples related to GC problems
• Software Currently Available
  • NHSE currently points to 200+ modules and packages
    • parallel processing tools
    • libraries of reuseable components
    • Grand Challenge prototype codes

Netlib -- Network access to mathematical software and data

Jack Dongarra

Univ. Tenn. and ORNL

Eric Grosse

AT&T Bell Labs, Murray Hill NJ

netlib

Started in 1985.
Motivated by the research community
Uses email for the distribution.
Has grown in popularity and scope.
Funded by the NSF and Bell Labs.

• The development of NETLIB was motivated by the need for cost-effective, timely distribution of high-quality mathematical software to the research community at large.

• The system was designed to send, by return electronic mail, requested routines together with subsidiary routines and any related documents or test programs supplied by the authors.

• Automatic mechanism for the disseminate of public domain software.

Try:

Collection includes:

Netlib provides the following features:

• There are no administrative channels to go through.
• Since no human processes the request, it is possible to get software at any time, even in the middle of the night.
• The most up-to-date version is always available.

• Individual routines or pieces of a package can be obtained instead of a whole collection.

Over around 10000 requests a day.

Software collection about 1 Gbytes

21K file in 330 libraries/directories

Interdisciplinary resource

• Software
• Parallel processing collection
• Data
• Tools
• Reports
• Documentation
• Benchmarks
• Journal information

Synchronization and Netlib Sites:

• Still in use and growing
• Mirrored at a number of sites
  • netlib2.cs.utk.edu
  • netlib1.epm.ornl.gov
  • research.att.com
  • netlib.no
  • unix.hensa.ac.uk
  • ftp.zip-berlin.de

Offshoots

Other sites running the netlib processor, but to support other databases:

• statlib@temper.stat.cmu.edu statistics
  
• tuglib@science.utah.edu TeX
  
• reduce-netlib@rand.org Reduce symbolic algebra
  
• maple-netlib@can.nl Maple symbolic algebra
  
• nistlib@cmr.ncsl.nist.gov benchmarks
  

Well over a hundred copies of netlib itself have been shipped.

NETLIB does not offer

• Technical assistance in determining and correcting problems with library software.

• Procedures for testing or validating codes.

• A uniform style for programming and documentation.

• Uniform error handling within the library.

The following types of software are being made available:

• Systems software and software tools.
  • compilers
  • message-passing communication subsystems
  • parallel monitors and debuggers.

• Basic building blocks for accomplishing common computational and communication tasks.
  • Building blocks are meant to be used by Grand Challenge teams

• Research codes that have been developed to solve difficult computational problems.
  • Many have been developed to solve specific problems
  • Serve as proofs of concept
  • Models for developing general-purpose reusable software

Netlib - Network Access to
Mathematical Software and Data

• Began in 1985
  • JD and Eric Grosse, AT&T Bell Labs

• Motivated by the need for cost-effective, timely distribution of high-quality mathematical software to the community.

• Designed to send, by return electronic mail, requested items.

• Automatic mechanism for the disseminate of public domain software.
  • Still in use and growing
  • Mirrored at a number of sites
    • netlib2.cs.utk.edu
    • netlib1.epm.ornl.gov
    • research.att.com
    • netlib.no
    • unix.hensa.ac.uk
    • ftp.zip-berlin.de

=6.in ../NSE295/netlib2.ps

=6.in ../NSE295/netlib-counts.ps

Multilevel Review System

• 0: Unreviewed Level
  • Growth through author-generated additions
  • Mechanical checks only

• 1: Partially Reviewed Level
  • Checks for consistency and completeness
  • Comparable to current review for Netlib
• 2: Reviewed Level
  • 2-6 outside reviewers
  • Addition to Road Map
  • Usability, robustness, documentation considered
• Simiilar to journal review process

Editorial Board

Technical and Political Issues

• How will the naive user find the right software?
  • Answer: Via the NHSE search/browser interface and the Road Map
• How will authentication, integrity, and version control be implemented?
  • Answer: By a publishing system that includes unique naming & digital signatures.
• Will the NHSE support distribution of software that is not free or cannot be freely distributed?
  • Answer: Yes, but...
    • only provide classification, review, and access
    • use of encryption and separate key distribution
    • NHSE will not have an accounting department

• Will the NHSE be responsible for support of software?
  • Answer: NO!
    • Any support will be by author (or appropriate agent)

Road Map

• Structured Knowledge Base on Software Components
  • Similar to a hypertext encyclopedia
  • Assembled with the help of panels of experts

• various-perspective catalog
  • Glossaries
  • Algorithms
  • Applications categories
  • Enabling software
  • Benchmarks
  • Hardware
  • Education and training
  • Links to other sites

• Prototype Currently Available
  • Topic: available applications codes and their component HPCC technologies

Different disciplines will maintain their own software repositories

• Users should not need to access each of these repositories separately

• NHSE will provide a uniform interface to a virtual HPCC software repository which will be built on top of the distributed set of discipline-oriented repositories.

• The interface will assist the user in locating relevant resources and in retrieving these resources.

• A combined browse/search interface will allow the user to explore the various HPCC areas and become familiar with the available resources.

• A longer term goal of the NHSE is to provide users with domain-specific expert help in locating and understanding relevant resources.

Research Issues

• Repository in a Box
  • Everything required for a site to setup a repository and get connected to the NHSE
    • publishing tools
    • ftp, http, gopher, email servers
    • logging and statistical tools
    • integration with replication service
    • guidence and support

• LIFN
  • assigned to a particular sequence of bytes,
  • once the assignment has been made, the same LIFN cannot subsequently be used to name any other sequence of bytes.

• Indexing and Searching
  • Currently very ad hoc
  • Harvest system provides a set of customizable tools

Needs for Browsing and Searching

• Current Web interfaces are difficult and frustrating for the user who is attempting to locate specific information.

• Browsing by following hypertext links is slow and can be disorienting.

• Keyword searching suffers from the vocabulary mismatch problem and is unsuitable for users with imprecise information and software needs.

Benefits

1. Faster development of high-quality software so that scientists can spend less time writing and debugging programs and more time on research problems.
2. Less duplication of software development effort by sharing of software modules.
3. Less time and effort spent in locating relevant software and information through the use of appropriate indexing and search mechanisms and domain-specific expert help systems.
4. Reducing information overload through the use of filters and automatic search mechanisms.

Overall Strategy for the NHSE:

• Effectiveness of the NHSE will depend on discipline-oriented groups and Grand Challenge teams having ownership of the discipline-oriented software repositories.

• The information and software residing in these repositories will be best maintained and kept up-to-date by the individual disciplines, rather than by centralized administration.

• Central administration will be used instead to handle interoperation and meet common needs.

• Although the various disciplines will have ownership of the repositories, they should not be expected to develop the software and tools for building, managing, and interfacing to their repositories.

• Much useful information retrieval (IR) software is currently available, both in the form of client and server programs (e.g., http servers and WWW browsers), as and this software should be incorporated into the NHSE.

Summary

• Initial implementation built on existing technologies
  • WWW
    • Distributed
    • Scalable
  • Netlib, etc
  • Rapid deployment

• Multilevel review and classification scheme
  • Unreviewed
  • Partially reviewed
  • Reviewed
• Road Map

Summary (continued)

• Measurement and evaluation
  • Statistics for unreviewed and partially reviewed
  • Evaluations for reviewed
• Outreach and technology transition
  • Educational activities aimed at the user community
  • Fostering technology development by industry
• Capitalization of emerging technologies
  • Foster transition from research to advanced development prototype
• Working on standardization within WWW community
  • member of RIG, IETF, IESG, WWW consort

Some Url's Related to Computational Science

• National HPCC Software Exchange
  http://www.netlib.org/nhse/

• NHSE Software Catalog
  http://www.netlib.org/nhse/sw_catalog/index.html

• Netlib Repository
  http://www.netlib.org/

• Computational Science Education
  http://www.netlib.org/nhse/cse_edu.html

• Books, Course Materials, and Tutorials
  http://www.netlib.org/nhse/cse_edu.html#books

• CS267 - Applications of Parallel Computers
  U.C. Berkeley CS267: Spring 1995 Jim Demmel
  http://www.icsi.berkeley.edu/cs267/

• 18.337 Parallel Scientific Computing
  MIT Spring, 1995 Alan Edelman
  http://web.mit.edu/18.337/WWW/home.html

• North Carolina State University
  Visualizations in Materials Science
  http://vims.ncsu.edu/cgi/index.acgi

• Computational Science Education Project
  http://csep1.phy.ornl.gov/csep.html

Who needs numerical software?

• Kinds of users and their priorities:
  • Engineers and scientists generally, who make 12,000 requests/day to netlib and keep NAG and IMSL in business:
    1. Easy interface, hidden details
    2. Reliability
    3. Speed
  • HPCC community, solving biggest and hardest problems:
    1. Speed
    2. Access to details for tuning
    3. Reliable enough for their application
  • Teachers and Students
    1. Ease of understanding
    2. Access to some details for learning
• Can we please everyone with one ``medium''?

=10.in ../CRPC.395/templates-flow.ps

Iterative Methods

• No single iterative method that can solve any given sparse linear system in reasonable time and with reasonable memory requirements.
• Rate of convergence depends on certain properties of the system, and these properties are often unknown in practice.
• For many very large linear systems, iterative methods are at this moment the only choice.
• Necessary to have a variety of iterative methods available.
• Through Templates the user is guided into the world of iterative methods, with only a minimum of linear algebra knowledge required.
• Using Templates the user can build software at several levels of sophistication, depending on requirements and goals.

Iterative Methods

• The iteration schemes consist of one or two matrix vector products, a couple of inner-products and a few vector updates.

• The algorithms also allow for some form of preconditioning, which means that in each step a linear system Mz=r has to be solved, where M has to be specified by the user.

• These operations are pretty well understood, and it is easy to see how the algorithms work.

• These basic iteration Templates may be used for simple computational experiments in order to get familiarized with the basic iteration methods and their mutual differences.

• The user is given extensive advice in the manual on how to expand the basic codes to reliable software for practical problems.

Motivation from Iterative Methods

Algorithm sketches for

• Gauss Siedel, Jacobi SOR, SSOR, etc.

• PCG, Bi-CG, QMR, GMRES, etc.

• Preconditioners

• Domain Decomposition

• Parallelism

\

Templates for Sparse Matrix Computations

• Alternate to software
• Describe the basic features of the algorithms
• Language not so important
• Communication between disciplines
• Clear documentation
• Test cases
• Provide understanding of the results
• Allow customization
• Serve as a pedagogical role
• Retain the delicate numerical details
• Describe parallel opportunities

A Template for an Algorithm Includes

1. A high-level description of the algorithm.
2. A description of when it is effective, including conditions on the input, and estimates of the time, space or other resources required. If there are natural competitors, they will be referenced.
3. A description of available refinements and user-tunable parameters, as well as advice on when to use them.
4. Pointers to complete or partial implementations, perhaps in several languages or for several architectures (each parallel architecture). These implementation expose those details suitable for user-tuning, and hide the others.
5. Numerical examples, on a common set of examples, illustrating both easy cases and difficult cases.
6. Trouble shooting advice.
7. Pointers to texts or journal articles for further information.

In addition to individual templates, there will be a decision tree to help steer the user to the right algorithm, or subset of possible algorithms, based on a sequence of questions about the nature of the problem to be solved.

Building Blocks
for Iterative Solution of Linear Systems

• Algorithm sketches for
  • Algorithm
    • Jacobi, Gauss-Seidel, SOR
    • CG, Precond-CG, CG-Squared, Bi-CG
    • Bi-CG-Stab, QMR, GMRES, Chebychev

  • Matlab script
  • Fortran code in a 2-D array
  • Fortran code using reverse commmunication
  • Preconditioners
    • Jacobi, SSOR, Incomplete Factoriation, Polynominal
  • Convergence tests
  • Performance Summary
  • Sparse Data Structures
  • Hints on parallel implementation
  • Available from SIAM or
    http://www.netlib.org/templates/index.html

Three Potential User Communities for such Tools

• The ``HPCC'' (High Performance Computing and Communication) community consists of those scientists trying to solve the largest, hardest applications in their fields. They desire high speed, access to algorithmic details for performance tuning, and reliability for their problem.

• Engineers and scientists generally desire easy-to-use, reliable software, that is also reasonably efficient.

• Students and teachers want simple but generally effective algorithms, which are easy to explain and understand.

=10.in ../TEMPLATES2/templates-eigenmat.ps =10.in ../TEMPLATES2/templates-flow.ps =10.in ../TEMPLATES2/templates-cg.ps

*     First time call always init.
      IJOB = 1
 
 1    CONTINUE
 
          CALL CGSREVCOM(N, B, X, WORK, LDW, ITER, RESID, INFO,
     $                   NDX1, NDX2, SCLR1, SCLR2, IJOB)
 
*         On a return from REVCOM() we use the table
*         to figure out what is reqd.
          IF (IJOB .eq. -1) THEN
*           revcom wants to terminate, so do it.
            GOTO 2
          ELSEIF (IJOB .eq. 1) THEN
*           call matvec.
            CALL MATVEC(SCLR1, WORK(NDX1), SCLR2, WORK(NDX2))
          ELSEIF (IJOB .eq. 2) THEN
*           call solve.
            CALL PSOLVE(WORK(NDX1), WORK(NDX2))
          ELSEIF (IJOB .eq. 3) THEN
*           call matvec with X.
            CALL MATVEC(SCLR1, X, SCLR2, WORK(NDX2))
         ELSEIF (IJOB .EQ. 4) THEN
*           do stopping test 2
*           if FirstTime, set info  so that BNRM2 is computed.
            IF( FTFLG ) INFO = -1
            CALL STOPTEST2(N, WORK(NDX1), B, BNRM2, RESID, TOL, INFO)
            FTFLG = .FALSE.
         ENDIF
*        done what revcom asked, set IJOB & go back to it.
         IJOB = 2
         GOTO 1
*     come here to terminate
 2    CONTINUE
*
      RETURN
*     End of CGS
      END

function [x, error, iter, flag] = cg(A, x, b, M, max_it, tol)
%  -- Iterative template routine --
%     Details of this algorithm are described in "Templates for the
%     Solution of Linear Systems: Building Blocks for Iterative
%     Methods", Barrett, Berry, Chan, Demmel, Donato, Dongarra,
%     Eijkhout, Pozo, Romine, and van der Vorst, SIAM Publications,
%     1993. (ftp netlib2.cs.utk.edu; cd linalg; get templates.ps).
%
%  [x, error, iter, flag] = cg(A, x, b, M, max_it, tol)
%
% cg.m solves the symmetric positive definite linear system Ax=b 
% using the Conjugate Gradient method with preconditioning.
% input   A        REAL symmetric positive definite matrix
%         x        REAL initial guess vector
%         b        REAL right hand side vector
%         M        REAL preconditioner matrix
%         max_it   INTEGER maximum number of iterations
%         tol      REAL error tolerance
% output  x        REAL solution vector
%         error    REAL error norm
%         iter     INTEGER number of iterations performed
%         flag     INTEGER: 0 = solution found to tolerance
%                           1 = no convergence given max_it
  flag = 0;  iter = 0;                      % initialization
  bnrm2 = norm( b );
  if  ( bnrm2 == 0.0 ), bnrm2 = 1.0; end
  r = b - A*x;
  error = norm( r ) / bnrm2;
  if ( error < tol ) return, end
  for iter = 1:max_it                       % begin iteration
     z  = M \ r;
     rho = (r'*z);
     if ( iter > 1 ),                       % direction vector
        beta = rho / rho_1;
        p = z + beta*p;
     else
        p = z;
     end
     q = A*p;
     alpha = rho / (p'*q );
     x = x + alpha * p;                    % update approximation vector
     r = r - alpha*q;                      % compute residual
     error = norm( r ) / bnrm2;            % check convergence
     if ( error <= tol ), break, end 
     rho_1 = rho;
  end
  if ( error > tol ) flag = 1; end         % no convergence
% END cg.m

=10.in ../TEMPLATES2/templates-eigen.ps =10.in ../TEMPLATES2/templates-eigensym.ps

• Mathematical Properties

• Desired Spectral Information

• Problem Representation

• Available Operations

Yes, we can please everyone!

{

• We propose that
  • NHSE - National High Performance Software Exchange
  • GAMS - Guide to Available Math Software
  • Netlib
  • Templates
  • NA textbooks
  • Annotated bibliographies
  • Computing environments á la Matlab or Maple
  • On-line compute servers (comp-u-bots) for bigger problems
  should all be part of one seamless whole.

• We propose an E-book containing
  • Linearly ordered text
  • Multiple access modes via hypertext
    • Table of contents of book
    • Index of book
    • A decision-tree querying the user to pick the right algorithm
    • Pointers to other trees (netlib, GAMS)
  • Multiple levels of algorithmic description
    • ``Template'' in pseudo-code, further pointers to common notation, etc.
    • One-page description of algorithm
    • Matlab implementation
    • Fortran, C, C++ implementations
    • Detailed text (references to literature)
      (``Numerical Linear Algebra'', Demmel)
    • Pointers to literature
• C++ implementation of LinSolve or EigSolve incorporating parts of decision tree (Pozo)
• Open architecture for future growth
• Hard-nosed editing for most reliable parts

}

Future Work

• Publically distribute detailed outline
  Superset of likely content

• Get (potential) user feedback
  (workshop planned)

• Keep linear version of book 200 pages
  (not all material)

• Q: Will a good design put NA faculty out of business?
  A: Better we do it than someone else.

Different users with different needs.

{

The traditional library users, who make 500 requests/day to netlib and keep NAG and IMSL in business, have the following priorities:

• Easy interface with hidden details
  
• Reliability; the code should fail as rarely as possible
  
• Speed
  

The HPCC community, on the other hand, which wants to solve the largest, hardest problems as quickly as possible, seems to want

• Speed
  
• Access to internal details to tune data structures to the application
  
• Algorithms which are fast for the particular application even if not reliable as general methods
  

Differing priorities

Different approaches to algorithms and software.

A Practical Solution: Meta-Libraries

• separate the data implementation details out of the fundamental algorithms

• describe library algorithms in terms of abstract base classes (inheritance)

• specify only the interface

• utilize late-binding (polymorphism) to determine data distributions and implementations

Need good design to choose proper objects and abstractions to balance

• performance
• reusability
• generality
• control
• flexibility

TEMPLATES -- REFERENCES

• Templates software and documentation for Ax=b can be obtained via:

  • WWW: http://www.netlib.org/templates,
  • (anonymous) ftp ftp.netlib.org:
    • cd templates; get index
  • email netlib@www.netlib.org with the message: send index from templates

• R. Barrett, M. Berry, T. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout, R. Pozo, C. Romine, H. van der Vorst, Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, PA, 1994.

• About this document ...