-
Complex Modeling of Matrix Parallel Algorithms
Issue:
Volume 3, Issue 5-1, September 2014
Pages:
1-14
Received:
14 July 2014
Accepted:
18 July 2014
Published:
31 July 2014
Abstract: Parallel principles are the most effective way how to increase performance in parallel computing (parallel computers and algorithms too). In this sense the paper is devoted to a complex performance evaluation of matrix parallel algorithms (MPA). At first the paper describes the typical matrix parallel algorithms and then it summarizes common properties of them to complex performance modeling of MPA. To complex performance analysis we are able to take into account all overheads influence performance of parallel algorithms (parallel computer architecture, parallel computation, communication etc.). To be le to analyze MPA in their abstract form we have defined needed decomposition models of MPA. For these decomposition strategies we derived analytical relation for defined complex performance criterions including isoefficiency functions, which allow us to predict performance although for hypothetical parallel computer. In its experimental part the paper considers the achieved results using defined complex performance criterions including issoefficiency function for performance prediction also for hypothetical future parallel computers. Such idea of common abstract analysis could be very useful in deriving complex performance criterions for groups of other similar parallel algorithms (PA) as for example numerical integration PA, optimization PA etc.
Abstract: Parallel principles are the most effective way how to increase performance in parallel computing (parallel computers and algorithms too). In this sense the paper is devoted to a complex performance evaluation of matrix parallel algorithms (MPA). At first the paper describes the typical matrix parallel algorithms and then it summarizes common proper...
Show More
-
Complex Performance Modeling of Parallel Algorithms
Peter Hanuliak,
Juraj Hanuliak
Issue:
Volume 3, Issue 5-1, September 2014
Pages:
15-28
Received:
14 July 2014
Accepted:
18 July 2014
Published:
31 July 2014
Abstract: Parallel principles are the most effective way how to increase parallel computer performance and parallel algorithms (PA) too. In this sense the paper is devoted to a complex performance evaluation of chosen PA. At first the paper describes very shortly PA and then it summarized basic concepts for performance evaluation of PA. To illustrate the analyzed evaluation concepts the paper considers in its experimental part the results for real analyzed examples of discrete fast Fourier transform (DFFT). These illustration examples we have chosen first due to its wide application in scientific and engineering fields and second from its representation of similar group of PA. The basic form of parallel DFFT is the one-dimensional (1-D), unordered, radix–2 algorithm which uses divide and conquer strategy for its parallel computation. Effective PA of DFFT tends to computing one – dimensional FFT with radix greater than two and computing multidimensional FFT by using the polynomial transfer methods. In general radix - q DFFT is computed by splitting the input sequence of size s into q sequences each of them in size n/q, computing faster their q smaller DFFT’s, and then combining the results. So we do it for actually dominant asynchronous parallel computers based on Network of workstations (NOW) and Grid systems.
Abstract: Parallel principles are the most effective way how to increase parallel computer performance and parallel algorithms (PA) too. In this sense the paper is devoted to a complex performance evaluation of chosen PA. At first the paper describes very shortly PA and then it summarized basic concepts for performance evaluation of PA. To illustrate the ana...
Show More
-
Modeling of Communication Complexity in Parallel Computing
Issue:
Volume 3, Issue 5-1, September 2014
Pages:
29-42
Received:
14 July 2014
Accepted:
18 July 2014
Published:
31 July 2014
Abstract: Parallel principles are the most effective way how to increase parallel computer performance and parallel algorithms (PA) too. Parallel using of more computing nodes (processors, cores), which have to cooperate each other in solving complex problems in a parallel way, opened imperative problem of modeling communication complexity so in symmetrical multiprocessors (SMP) based on motherboard as in other asynchronous parallel computers (computer networks, cluster etc.). In actually dominant parallel computers based on NOW and Grid (network of NOW networks) [31] there is necessary to model communication latency because it could be dominant at using massive (number of processors more than 100) parallel computers [17]. In this sense the paper is devoted to modeling of communication complexity in parallel computing (parallel computers and algorithms). At first the paper describes very shortly various used communication topologies and networks and then it summarized basic concepts for modeling of communication complexity and latency too. To illustrate the analyzed modeling concepts the paper considers in its experimental part the results for real analyzed examples of abstract square matrix and its possible decomposition models. These illustration examples we have chosen first due to wide matrix application in scientific and engineering fields and second from its typical exemplary representation for any other PA.
Abstract: Parallel principles are the most effective way how to increase parallel computer performance and parallel algorithms (PA) too. Parallel using of more computing nodes (processors, cores), which have to cooperate each other in solving complex problems in a parallel way, opened imperative problem of modeling communication complexity so in symmetrical ...
Show More
-
Modeling of Parallel Computers Based on Network of Computing
Issue:
Volume 3, Issue 5-1, September 2014
Pages:
43-56
Received:
14 July 2014
Accepted:
18 July 2014
Published:
31 July 2014
Abstract: The optimal resource allocation to satisfy such demands and the proper settlement of contention when demands exceed the capacity of the resources, constitute the problem of being able to understand and to predict system behavior. To this analysis we can use both analytical and simulation methods. Modeling and simulation are methods, which are commonly used by performance analysts to represent constraints and to optimize performance. Principally analytical methods represented first of all by queuing theory belongs to the preferred method in comparison to the simulation method, because of their potential ability of general analysis and also of their ability to potentially analyze also massive parallel computers. But these arguments supposed to develop and to verify suggested analytical models. This article goes further in applying the achieved analytical results in queuing theory for complex performance evaluation in parallel computing [9, 14]. The extensions are mainly in extending derived analytical models to whole range of parallel computers including massive parallel computers (Grid, meta computer). The article therefore describes standard analytical model based on M/M/m, M/D/m and M/M/1, M/D/1 queuing theory systems. Then the paper describes derivation of the correction factor for standard analytical model, based on M/M/m and M/M/1 queuing systems, to study more precise their basic performance parameters (overhead latencies, throughput etc.). All the derived analytical models were compared with performed simulation results in order to estimate the magnitude of improvement. Likewise they were tested under various ranges of parameters, which influence the architecture of the parallel computers and its communication networks too. These results are very important in practical use.
Abstract: The optimal resource allocation to satisfy such demands and the proper settlement of contention when demands exceed the capacity of the resources, constitute the problem of being able to understand and to predict system behavior. To this analysis we can use both analytical and simulation methods. Modeling and simulation are methods, which are commo...
Show More
-
Modeling of Single Computing Nodes of Parallel Computers
Peter Hanuliak,
Michal Hanuliak
Issue:
Volume 3, Issue 5-1, September 2014
Pages:
57-69
Received:
16 July 2014
Accepted:
18 July 2014
Published:
31 July 2014
Abstract: The paper describes analytical modeling for single computing nodes of parallel computers. At first the paper describes very shortly the developing steps of parallel computer architectures and then he summarized the basic concepts for performance evaluation. To illustrate theoretical evaluation concepts the paper considers in its experimental part the achieved results on concrete analyzed examples and their comparison. The suggested analytical models consider for single computing node based on processor or core and SMP modeling of own computer node´s activities and node´s communication channels of performed data communications within computing node queuing theory systems M/D/m or M/D/. In case of using SMP parallel system as node computer the suggested models consider for own node’s activities M/M/m or M/D/m queuing theory systems. Although we are able to use other more complicated queuing theory systems we prefer modeling with mentioned models because achieved results for these models we can use in decomposed modeling of coupled computing nodes as network of workstations (NOW) or network of massive NOW modules (Grid). The achieved results of the developed analytical models we have compared with the results of tested computing nodes with other alternative evaluation method based on suitable benchmarks to verify developed analytical models. The developed analytical models could be used under various ranges of input analytical parameters, which influence the architecture of analyzed computing nodes which are interested for the praxis.
Abstract: The paper describes analytical modeling for single computing nodes of parallel computers. At first the paper describes very shortly the developing steps of parallel computer architectures and then he summarized the basic concepts for performance evaluation. To illustrate theoretical evaluation concepts the paper considers in its experimental part t...
Show More
-
Decomposition Models of Parallel Algorithms
Michal Hanuliak,
Juraj Hanuliak
Issue:
Volume 3, Issue 5-1, September 2014
Pages:
70-84
Received:
16 July 2014
Accepted:
18 July 2014
Published:
31 July 2014
Abstract: The article is devoted to the important role of decomposition strategy in parallel computing (parallel computers, parallel algorithms). The influence of decomposition model to performance in parallel computing we have illustrated on the chosen illustrative examples and that are parallel algorithms (PA) for numerical integration and matrix multiplication. On the basis of the done analysis of the used parallel computers in the world these are divided to the two basic groups which are from the programmer-developer point of view very different. They are also introduced the typical principal structures for both these groups of parallel computers and also their models. The paper then in an illustrative way describes the development of concrete parallel algorithm for matrix multiplication on various parallel systems. For each individual practical implementation of matrix multiplication there is introduced the derivation of its calculation complexity. The described individual ways of developing parallel matrix multiplication and their implementations are compared, analyzed and discussed from sight of programmer-developer and user in order to show the very important role of decomposition strategies mainly at the class of asynchronous parallel computers.
Abstract: The article is devoted to the important role of decomposition strategy in parallel computing (parallel computers, parallel algorithms). The influence of decomposition model to performance in parallel computing we have illustrated on the chosen illustrative examples and that are parallel algorithms (PA) for numerical integration and matrix multiplic...
Show More
