METHODS, TOOLS AND ALGORITHMS FOR HIGH-ACCURACY COMPUTATIONS IN PARALLEL SYSTEMS

Team manager: Dr. Alexander P. Vazhenin
Position: Senior Researcher
Department: Supercomputer Software
Organization: Computing Center
Siberian Division
Organization Address: 6, Lavrentiev Ave.
Novosibirsk, 630090
Russia
Phone: (3832) 350994
Facsimile: (3832) 357942 or (3832) 324259
E-mail: vazhenin@ssd.sscc.ru

The goal of this work is to design software tools supporting Superprecision Parallel ARiTHmetic computations (SPARTH) in modern supercomputers, to estimate the possibilities of these systems, and to develop the high-accuracy parallel algorithms for solving some applied problems.

OBJECTIVES

One of important factors impacting on the accuracy of data processing is rounding in arithmetic operations. The necessity of rounding is caused by fixed and relatively small length of operands in most computers. It is important to note also that parallel algorithms used in modern supercomputers are effective in reaching very high performances. However, they are actually noneffective in minimizing the rounding errors for operations of single or double precision format.

The goal of this work is to develop software tools supporting Superprecision Parallel ARiTHmetic computations (SPARTH) in modern supercomputers and to estimate the possibilities of these systems. The main directions of these investigations are:

Note also, that the solution of applied problems will be implement by the following stages:

Therefore, the SPARTH-library have to support mixed computations using both the traditional data representation and special SPARTH-numbers.

The SPARTH-SIMD library

The architecture

An example of SIMD-approach is software tools for Super-precision Parallel AriTHmetic designed for a fine-grained SIMD-system ES-2720. This computer has the architecture similar to the STARAN associative array processor. From the user's viewpoint, this programming system represents as a virtual vector processor with the programmable length of vector operands named SPARTH-processor. Figure shows main elements of this architecture.

Features of SPARTH-processor

Computations in the SPARTH-processor may be performed in two modes: with the fixed or dynamic accuracy. The first mode is characterized by the constant capacity of operands in computations. In this case, the number of available vector registers is determined by required capacity. The user is able to choose between the problem solution rate, the amount of processed data and required accuracy.

In the dynamic accuracy mode, the operand capacity may be altered in the interval defined by the user. The number of available vector registers is formed according to the maximum ordered capacity value. Computations may be started with relatively small capacity of operands. If needed,the SPARTH-processor may be switched to a next capacity limit by means of precision control procedures.

In the SPARTH-processor three types of data are used:

Processor instructions provide effective interaction of its subsystems and execution of high-precision parallel computations. Arithmetic operations are executed in two stages. At first, the exact result (without rounding) is formed in HPS, then it is stored into destination registers using the rounding operations for multiplication and division. In the dynamic accuracy mode, the data located in HPS may be stored without rounding. The peculiarity of the library implementation is that it is reduced to few basic operations, which execute structural transformations of vectors, and special types of computations. This allows effective mapping of algorithms on VPS-architecture.

The other example is a SPARTH-library, which is an extension of C-language. It supports the programming of computations with dynamically changed length of operands in MIMD-systems based on Message Passing Interface (MPI). Some implemented experiments show that this library can be considered as the portable program package.

Data formats

The fixed format is usually good enough to perform almost all of the computations but there is a `narrow' place where each operation needs to be calculated as accurate as possible. Therefore, we have developed a special data format containing both fixed and varying in length structures. Each number is written in the direct code. The integer part is separately kept from the fractional one. There is also a special pole where the sign of the number is contained. Performing start initialization, one can choose sizes of fixed blocks as well as it is in SIMD-realization.

As shown in Figure, each number has three parts. We call two of them standard parts (sign and std_int, std_frac). These parts are created only when the number is initialized. They represent solid memory blocks. Doing this, we attempt to reduce fragments of the memory and number of Operation System requests for open/close operations.

Dynamic change of operand length is realized by producing additional, so called non-standard parts which combined to one-joined structure. Every block of this type has the area of information, and the pointer to the next block (point_int and point_frac). The number of non-standard blocks is kept in the special poles.

Implementation of arithmetic operations

Every arithmetic operation is calculated as follows. The variable ACCURACY stated before the operation means the number of the significant digits needs to get the result. Operation result is obtained into the special buffer without rounding. Then, this result will be stored into the destination operand as shown in Figure.

NOTE

The non-standard integer part will not be reduced. We allow to increase the absolute number value as high as it is possible in the system. There is no overflow in a library.

The main topics

The SPARTH-MIMD library is developed as an extension of C-language. This library can support both sequential (in one processor) and parallel computations with dynamically changed length of operands. The library programs include the following:

Numerical algorithms and experiments

A number of new parallel algorithms were developed for solving problems of linear algebra:

The SPARTH-libraries contain also a set of standard procedures implementing the following operations:

SPARTH-SIMD library was realized on the associative array processor ES-2720, the architecture of which is similar to STARAN, and has the following characteristics: the PEs number of m=256, the size of local memory in each processing channel of s=4096. This approach can be used as well for other fine-grained SIMD-systems (DAP, MPP, CM-1, CM-2, etc.).

At first, SPARTH-MIMD library was produced for a multitransputer system containing five processors T800/20. This library was ported also to the PowerX'Plorer system of Parsytec including the Sun-5 workstation as a host and 8 computing nodes. Each nodes consists of the T805 transputer and PowerPC-601 processor. The sequential high-accuracy algorithms were investigated on the IBM PC/486 and Pentium computers, and the pipeline processor of INTEL/860. This confirms that it can be considered as a portable programming system.

APPLIED PROBLEMS

We are investigating the solution the following problems by means of SPARTH-library.

LINEAR ALGEBRA PROBLEMS

Linear Algebra is a basis for solving many applied problems. A list of some high-accuracy parallel algorithms was shown above. The future investigations are oriented to extend a set of these algorithms. We are going to develop the algorithms and programs for solving the following problems: eigenvalue problems; matrix inversion; Kholessky decomposition; sparse systems of linear equations.

MATHEMATICAL PHYSIC

The nonstationary problems of mathematical physic require to solve the large sparse systems of linear equations containing ill-conditioned matrices. Usually, the iterative methods are used for solving these systems. One such approach is the method of partial factorization combined with conjugate gradient method. This can allow the high speed of convergence of iterative process. We are going to investigate an impact of rounding errors on the solution time as well as to improve the final accuracy by increasing both the problem size and operand capacity.

VISUAL GEOMETRY AND TOPOLOGY

Recent achievements of visual geometry and topology made nontrivial mathematical concepts understable and applicable. In some cases the dynamically changed length of operand can support accurate intermediate computations. For example, the extraction of ridges and ravines of a surface is based on differential geometry of the surface. Calculations of many partial derivatives (up to fourth order) are essential to implement this procedure. Therefore, the standard data formats can be not good enough if the surface is very complex.

PARTICLE-IN-CELL METHOD and N-BODY PROBLEMS

Usually, the systems being investigated consist of many elements which interact with other through gravitational, magnetic or electric force. Its evolution can be calculated by integrating simultaneous differential equations for the large number of particles. In this case, the basic operations will be dot products or sums of large size. This requires very long operands to obtain the accurate result.

REFERENCES

  1. A.Vazhenin. Efficient High-accuracy Computations in Massively Parallel Systems. Proc. "Workshop on Parallel Scientific Computing PARA94L", 1994, Lyngby, Denmark. Springer-Verlag, 1994, Lecture Notes in Computer Science. Vol. 879, pp. 505-519.
  2. A.Vazhenin, N.Mirenkov. SCORE: Scientific Computers for Overcoming Rounding Errors. PARALLEL COMPUTING: Trends and Applications, North-Holland, Elsevier Sci. Publ. Co., the Netherlands, 1994, pp. 347-354.
  3. A.Vazhenin. Hardware and Algorithmic Support of High-accuracy Computations in Vertical Processing Systems. Proceedings of International Conference "Parallel Computing technologies", August 30 - September 4, 1993, Obninsk, Russia, pp. 149-162.
  4. A.Vazhenin. Parallel Algorithm for Solving Systems of Linear Equations with Dynamically Changed Length of Operands. Proc. "The First Aizu International Symposium on Parallel Algorithms/ Architecture Synthesis", 1995, Aizu-Wakamatsu, Fukushima, Japan. IEEE Comp. Soc. Press, Los Alamitos, California. pp. 100-106.
  5. A.Vazhenin, V.Morosov. Parallel Iterative Solution of Systems of Linear Equations with Dynamically Changed Length of Operands. Proc. of the International Conference "Parallel Computing Technologies (PaCT-95)", September 1995, San-Petersburg, Russia. Springer- Verlag, 1995, Lecture Notes in Computer Science. Vol. 964, pp. 294-303.