The work considers an approach to the adaptation of applications that use algorithms proven to be successful and developed with the help of computers that do not have a high degree of parallelism, though in a number of implementations they require a sharp reduction in the computing time. A natural way-out is to transfer the algorithm solution to a highly parallel heterogeneous processing environment, i.e. hybrid supercomputer. Unfortunately, the result does not always meet expectations. The challenge is the need to consider architectural features of the supercomputer and the corresponding translation of the generic algorithm, while maintaining its semantic features, i.e. the development of parallel software of the generic algorithm scalable to allocated supercomputer resources. Available approaches to the software parallelization deliver superb results when algorithms demonstrate obvious parallelism. Otherwise, their transformation to the parallel representation requires an analysis of dependencies in parallel threads on data and costs of the parallel supercomputer execution. In this paper, we present an algorithm analysis technique that allows to determine fragments for a signi cant reduction in the computing time during the parallel execution. The result is a algorithm speci cation work schedule that ensures the e ective solution, using the supercomputer. The schedule is used to create the dedicated control over the execution of an parallelized algorithm for its e ective solution with the help of hybrid supercomputer resources. The work shows results of the implementation of the developed technique in terms of the genetic research.
There are currently a variety of areas of concern, where processing and analysis of large data arrays are actively used. For example, these include bioinformatics, photograph-based modeling of the surface relief, analysis of data on industrial plots for the optimization of manufacturing processes, etc. These areas have applications with algorithms that have proven to be successful in data processing of signi cantly smaller arrays, developed with the help of computers that do not have a high degree of parallelism. As a rule, capacities of such algorithms do not meet modern requirements for processing of huge data arrays and a sharp reduction in the time of the computation result output.
This work considers an adaption approach to applications that use successfully tested algorithms for the highly-parallel processing environment, namely the supercomputer. Unfortunately, the direct transfer result does not always meet expectations. The challenge is the need to consider architectural features of the supercomputer and the corresponding translation of the generic algorithm, while maintaining its semantic features, i.e. the development of parallel software of the source algorithm scalable to allocated supercomputer resources. 2
When analyzing available papers devoted to the software adaptation to hybrid supercomputer clusters, certain problems speci c to the hybrid cluster application programming model shall be considered: { a problem of the resource allocation dynamic control, { a problem of the task execution control especially in heterogeneous clusters, { a problem of the software adaptation for the e ective execution in several clusters based on the required load.
There are well-known publications devoted to the solution of these tasks.
Work [
This work presents an approach to the application adaptation based on its
preliminary static analysis and the generation of an e ective execution schedule
in view of the architecture of the hybrid supercomputer and application
requirements for cluster resources.
The speci c contribution of this paper is an approach that allows to run Java
parallel applications across completely di erent HPC systems (hybrid
supercomputer). As such, we developed a parallel version of MarkDuplicates, a
bioinformatics tool from Picard toolkit [
With regard to the principal di erences between our HPC systems, that caused the development of our approach, the computational part is performed on a traditional Linux cluster, while big data processing occurs directly in the global shared memory of the ccNUMA system. The division of tasks between systems is caused by complexity in providing Java support for huge pages and logically indivisible piece of RAM more than 2Tb. It is important to note that despite the variety of parallel computing models used in HPC, such as the traditional MPI+X paradigm or emerging parallel programming models like UPC/Charm++/X10, etc., we are forced to use Java for big data processing in this case because of existing Java codebase in bioinformatics. At the same time, we were not able to store terabyte les in the memory of the standard cluster node, which is equipped with only 60-256Gb RAM. We could use traditional not-in-memory network storage, but the interconnect latency ruins the performance gain, because the communication operations far outweigh the computational ones. The results of applying the developed approach to our systems will also be mentioned in Section 6. Thus we perform computational operations and processing of large data in hybrid environment of di erent systems, depending on their suitability. This approach has signi cant advantages since in-memory data processing is still the fastest pathway.
The above circumstances prompted us to develop the following procedure
to analyze the algorithm in order to search for program modules that will give
a signi cant reduction in the computing time for the parallel execution,
corresponding to the program correction that increases the degree of parallelism and
creates the execution schedule to ensure the e ective solution with the help of
the supercomputer. The procedure stipulates the following stages of analysis:
1. Call tree analysis of algorithm methods obtained as a result of pro ling
of an unadapted MarkDuplicates version to determine approaches, whose
call percentage is signi cant in the application. Figure 1 illustrates the
result of the tree analysis, which is the identi cation of a list of methods
with the highest frequency of calls. There are 4 methods in the
application under consideration: SAMFileWriterImpl.addAlignment (48.9%),
SamReader$AssertingIterator.next (33.8%), buildReadEnds (6.9%) and
getLibraryName (5.9%). The contribution of remaining used methods is
insignificant in terms of parallelization.
2. The algorithm correction through (initial or additional) parallelization of
commonly used methods. During parallelization, dependencies in terms of
data and control in parallel threads shall be considered with the provision of
the proper synchronization. There are well-known computerized approaches
to the search and analysis of dependencies [
There are a lot of well-known papers devoted to the task thread management
in high performance computing (HPC) [
The schedule formalization can be carried out in a number of ways. The work
gives preference to the use of standardized control language UCM [
Start
Task 1
Task 2
Task 3
Task 4
Task 5
End The schedule allows the task scheduler to distribute tasks both across resources of one cluster, and across resources of di erent clusters of the hybrid supercomputer. 5
An important feature of the e cient solution of parallel applications under study is the opportunity to use di erent node types of the hybrid supercomputer, depending on the stage of data processing and varying costs associated with the processing. Di erent operation stages of the same scienti c application include (1) compute-bound tasks, whose arithmetic operations greatly exceed the volume of communication operations, (2) bandwidth-bound tasks with predictable and successive access to the memory, (3) latency-bound tasks. The last type of tasks is characterized by high requirements for the size of the logically monolithic space of the globally addressable memory, intensive irregular addresses to the memory and poor spatial and temporal localization. The cost of the last task type dictates the need for a substantial increase in the memory of a single computing node if compared with pure computing tasks. This circumstance is stipulated by the processing task of large indivisible data because the computing system shall simultaneously meet requirements of parallel applications with high-computing intensity and requirements of applications from the big-data domain with high overhead costs of communications. To overcome restrictions of the memory space of one node in the hybrid supercomputer, it is possible to use multicomputer nodes with NUMA architecture (Non-Uniform Memory Access) equipped with RAM up to logically indivisible 12Tb for storage and processing of data used by MarkDuplicates application.
The memory non-uniformity inevitable in this case creates complex problems that shall be considered when adapting a parallel application to avoid sharp performance degradation. The main problems include (1) a computing node cache coherence problem, (2) a memory hot-spotting problem, (3) a false sharing problem. Furthermore, in case of Java-application for large data processing, di culties may arise in handling memory space exceeding 12Tb, as a result of non-uniform remote access when working with large memory pages.
The cache coherence problem [
Hot-spot memory contention [
False sharing in a multi-threaded Java-application means that there is addressing to di erent objects that share a common cache memory block. False sharing e ects can be mitigated with the help of the distribution based on the object creation time. However, when it comes to global shared memory nodes whose number of cores exceeds 3000, it can not be guaranteed that this e ect will be completely avoided. 6
Experimental results of the proposed technique are shown using MarkDuplicates metric computation are given in the table 1 for the solution of serial (not parallelized) and scalable algorithm versions in Java. JVM Java HotSpot 64-bit Server VM in 25.102-b14 build for linux-amd64 have been used in the computation. We ran our experiments across multicluster hybrid supercomputer, which includes (1) global shared memory system (cc-NUMA architecture) and (2) RSC Tornado cluster, installed at Supercomputer Center, SPbPU. We used multimachine cc-NUMA macronodes with up to 12Tb of RAM for storing input les directly to memory. The second system, Tornado cluster, is equipped with a 1336 CPUs (Intel Xeon E5-2697 v3) and is used primarily for high-performance data processing. Computation time spans for the scalable version managed by the schedule at the solution in 1 and 2 clusters, and the serial (not parallelized) version were compared. Time spans were obtained during tests in the processing of data, whose array exceeds 200Gb. The resulting one-order di erence demonstrates advantages of the proposed approach.
Similar results were obtained for a wide range of genetic algorithms. It should be noted that the C++ implementation of genetic algorithms and the use of OpenMP/MPI would lead to much better results, but biologists prefer Java, and formal code transformation without regard to problem semantics is unpromising. Finally, it should be noted that the acceleration of genetic research is an important factor for the results application in the clinical practice. 7
The scope of the proposed technique application is, in the rst place, processing algorithms for large data because the analysis of algorithms is usually costly and cannot be fully computerized. Therefore, the application of the technique is justi ed for repeatedly-used algorithms. For example, algorithms of genetic studies that should be quickly carried out in the medical practice. The technique is still studied, and its real application is so far limited to search and n-wise algorithms in C++ and Java,for which there are su ciently powerful pro lers. Nevertheless, it shows good results in the adaptation of algorithms created regardless of solution speci cs in a highly parallel supercomputer environment.
The main drawback of the technique is its labor-intensive implementation.
Therefore, it is planned in the future to computerize analysis tools for
application algorithms to facilitate their better parallelization, to computerize the
generation algorithm of schedules based on architectural features and resources
of the execution environment. Create a single in-process chain and appropriate
tools to computerize the adaptation of algorithms for the e cient execution in
the hybrid supercomputer [
Acknowledgments. This work was nancially supported by the Ministry of Education and Science of the Russian Federation within the framework of the state assignment № 29517.2017/64 (the project theme \Methods and technologies for veri cation and development of software for modeling and calculations using HPC platform with extramassive parallelism"). The results were obtained using ccNUMA system and RSC Tornado cluster in Supercomputer Center of Peter the Great St.Petersburg Polytechnic University.