2019 № 2(43)

CONTENTS

1. Platov G.A., Raputa V.F., Krupchatnikov V.N., Golubeva E.N., Malakhova V. V., Lezhenin A. A., Borovko I. V., Krylova A. I., Iakshina D. F., Krayneva M. V., Kravchenko V. V., Korobov O. A. Creation and development of a multicomponent complex of models of the Earth hydrodynamic processes

2. Snytnikova T. V. Evolution of associative parallel architectures

3. Azhbakov A. A.. Perepelkin V. A. Development and implementation of distributed portable algorithms of fragmented programs execution on heterogeneous multicomputers

Platov* G.A., Raputa* V.F., Krupchatnikov*^,** V.N., Golubeva* E.N., Malakhova* V. V., Lezhenin* A. A., Borovko* I. V., Krylova* A. I., Iakshina* D. F., Krayneva* M. V., Kravchenko* V. V., Korobov**^,*** O. A.

* Institute of Computational Mathematics and Mathematical Geophysics, SB RAS, 630090, Novosibirsk, Russia

**Siberian Regional Hydro meteorological Research Institute, ROSHYDROMET, 630099, Novosibirsk, Russia

***Novosibirsk State University, 630090, Novosibirsk, Russia

CREATION AND DEVELOPMENT OF A MULTICOMPONENT COMPLEX OF MODELS OF THE EARTH HYDRODYNAMIC PROCESSES

UDK 551.588:519.63

Since the foundation of the Computing Center (now the Institute of Computational Mathematics and Mathematical Geophysics — ICM&MG), the direction associated with the modeling of processes in the atmosphere, hydrosphere and cryosphere of the Earth has actively developed in Novosibirsk. A. S. Alekseev strongly supported this scientific activity and was the author of the idea of developing a single complex for the Earth system, including the lithosphere. One way or another, but the development of modern modeling is confidently moving in this direction. Previously, the models participating in CMIP projects of the IPCC program had the abbreviation CSM — Climate System Model, now a significant part of such models are earth system models, that is, ESM.

The problem of studying the Earth’s climate has been at the center of attention for several decades and has recently become particularly acute due to the so-called „global warming". The increase in air temperature during the past century was about 0.74 degrees on average, and approximately two thirds of this value were made during the period 1980-2000. A change in temperature by such an insignificant amount, which may not be felt, causes a number of more significant effects in the climate system. One of the most striking manifestations of „global warming" is the rapid decline in the ice mass of the Earth, both mountain and continental glaciers, and floating ice. The fact that a significant part of the Arctic as a result of seasonal fluctuations in the summer is completely free of ice requires a comprehensive study to understand the new conditions of habitat formation and economic activity.

However, the climate problem is not the only one which requires an integrated approach. There are a number of tasks, perhaps not so large-scale, but no less important. Data analysis and monitoring of the distribution of harmful impurities in the atmosphere and in the aquatic environment, contamination of soil and water bodies also require close attention because they are associated with the study of the conditions of human existence and activity, with the formation of sustainable environmental management and economic development.

In this article we will present a review of the current state of research in the ICMMG SB RAS in the direction of mathematical modeling of processes in the atmosphere, hydrosphere and cryosphere of the Earth.

Key words: Mathematical modeling, climate system, environmental monitoring.

References

1. Fraedrich К., Jansen Н., Kirk Е., Luksch U. and Lunkeit F. The Planet Simulator: Towards auser friendly model // Meteorol. Zeitschrift. 2005. N 14. P. 299-304.

2. Lunkeit F., Bottinger M., Fraedrich K., Jansen H., Kirk E., Kleidon A. and

Luksch U. Planet Simulator Reference Manual Version 15.0. 2007. [Electron. Res.]:

http: / / epic.awi.de/29588/1/Lun2007d.pdf.

3. Petoukhov V., Ganopolski A., Brovkin V., Claussen M., Eliseev A. and Kubatzki S. Rahmstorf CLIMBER-2: a climate system model of intermediate complexity. Part I: model description and performance for present climate // Climate Dynamics. 2000. N 16 (1). P. 1-17.

4. Brovkin V., Claussen M., Driesschaert E., Fichefet T., Kicklighter D., Loutre M. F., Matthews H.

D.,Ramankuttv N., Schaeffer M. and Sokolov A. Biogeophvsical effects of historical landcover changes simulated by six Earth system models of intermediate complexity // Clim. Dvnam. 2006 . N 26. P. 587-600.

5. Claussen M. et al. Earth system models of intermediate complexity: closing the gap in thespectrum of climate system models. Clim. Dvnam. 2002. N 18. P. 579-86.

6. Krupchatnikov V., Kuzin V., Golubeva E., Martynova Yu., Platov G. and Krylova A. Hydrology and Vegetation Dynamics of the Climate System of Northern Eurasia and the Arctic Basin // Izvestiva Atmospheric and Oceanic Physics. 2009. N 45 (1). P. 116-36.

7. Martynova Yu V, Krupchatnikov V N 2010 A study of the sensitivity of the surface temperature in Eurasia in winter to snow-cover anomalies: The role of the stratosphere // Izvestiva Atmospheric and Oceanic Physics. 2010. N 46 (6). P. 757-69.

8. Martynova Yu. V., Krupchatnikov V. N. Peculiarities of the Dynamics of the general atmospheric circulation in conditions of the global climate change // Izvestiva Atmospheric and Oceanic Physics.

2015. N 51 (3). P. 299-310.

9. Borovko I. V. and Krupchatnikov V. N. Responses of the Hadley cell and extra tropical troposphere stratification to climate changes simulated with a relatively simple general circulation model // Numerical Analysis and Applications. 2015. N 8 (1). P. 23-34.

10. Eliseev V., Coumou D., Chernokulskv A. V., Petoukhov V. and Petri S. Scheme for calculation of multi-layer cloudiness and precipitation for climate models of intermediate Geosci // Model.Dev.

2013. N 6. P. 1745-65.

11. Comiso J. C., Parkinson C. L., Gersten R. and Stock L. Accelerated decline in the Arctic sea ice cover // Geophvs. Res. Lett. 2008. N 35. L01703.

12. Bekrvaev R. V., Polyakov I. V. and Alexeev V. A. Role of polar amplification in long-term surface air temperature variation and modern Arctic warming //J. Climate. 2010. N 23. P. 3888-906.

13. Comiso J. C. Large decadal decline of the Arctic multiyear ice cover //J. Climate. 2012. N 25. P. 1176-93.

14. Screen J. A. and Simmonds I. The central role of diminishing sea ice in recent Arctic temperature amplification // Nature. 2010. N 464. P. 1334-37.

15. Cohen J. et al. Recent Arctic amplification and extreme mid-latitude weather // Nat. Geosci.

2014. N 7. P. 627-37.

16. Yeager, S. G., and Large W. G. CORE.2 Global Air-Sea Flux Dataset. Research Data Archive at the National Center for Atmospheric Research, Computational and Information Systems Laboratory. 2008. doi: 10.5065/D6WH2N0S.

17. Jaiser R., Dethloff K., Handorf D., Rinke A. and Cohen J. Impact of sea ice cover changes on the Northern Hemisphere atmospheric winter circulation // Tellus. 2012. N 64A. 11595.

18. Francis J. A. and Vavrus S. J. Evidence linking Arctic amplification to extreme weather in mid-latitudes // Geophvs. Res. Lett. 2012. N 39. L06801 doi:10.1029/2012GL051000.

19. Francis J. A. and Vavrus S. J. Evidence for a waiver jet stream in response to rapid Arctic warming // Environ. Res. Lett. 2015. N 10. 014005. doi:10.1088/1748-9326/10/1/014005.

20. Overland J., Francis J. A., Hall R., Hanna E., Kim S. J. and Vihma T. The melting Arctic and midlatitude weather patterns: are they connected? // J. Clim. 2015. N 28. P. 7917-32.

21. Shepherd T. G. Effects of a warming // Arctic Science. 2016. N 353. P. 989-90.

22. Overland J. E., Dethloff K., Francis J. A., Hall R. J., Hanna E., Kim S-J., Screen J. A., Shepherd T. G.,Vihma T. Nonlinear response of midlatitude weather to the changing // Arctic Nat. Clim. Change. 2016. N 6. P. 992-99.

23. Petoukhov V., Rahmstorf S., Petri S. and Schellnhuber H. J. Quasi resonant amplification of planetary waves and recent Northern Hemisphere weather extremes // Proc. Natl. Acad. Sci. 2013. USA110. P. 5336-41.

24. Platov G., Krupchatnikov V., Martynova Yu., Borovko I. and Golubeva E. A new earth’s climate system model of intermediate complexity, PlaSim-ICMMG-1.0: description and performance // IOP Conf. Ser.: Earth Environ. Sci. 2017. N 96. 012005.

25. Golubeva E. N., Platov G. A. and Iakshina D. F. Numerical simulations of the current state of waters and sea ice in the Arctic Ocean // Lbdisneg. 2015. N 2 (130). P. 81-92, doi: 10.15356/20766734-2015-2-81-92.

26. Beszczvnska-Moller, A., Fahrbach, E., Schauer, U., and Hansen, E. Variability in Atlantic water temperature and transport at the entrance to the Arctic Ocean, 1997-2010 // ICES J. Mar. Sci. 2012. N 69. P. 852-863.

27. Golubeva, E. N. and Platov G. A. On improving the simulation of Atlantic Water circulation in the Arctic Ocean // J. Geophvs. Res. 2007. 112, C04S05, doi:10.1029/2006JC003734.

28. Steele M., Morley R., Ermold W. PHC: A global hydrography with a high quality Arctic Ocean // J. Climate. 2000. V. 14. N 9. P. 2079-2087.

29. Beszczvnska-Moller, Agnieszka, 0vsteinSkagseth, Wilken-Jon von Appen, Waldemar Walczowski. Vidar Lien Splitting of Atlantic water transport towards the Arctic Ocean into the Fram Strait and Barents Sea Branches-mechanisms and consequences // Geophysical Research Abstracts.

2016. Vol. 18, EGU2016-15059.

30. Schauer, U., Beszczvnska-Moller A., Walczowski W., Fahrbach E., Piechura J., and Hansen E. Variation of measured heat flow through the Fram Strait between 1997 and 2006 // Arctic-Subarctic Ocean Fluxes. 2008. P. 65-85.

31. Polyakov, I., Timokhov, L., Alexeev, V., Bacon, S., Dmitrenko, I., Fortier, L., et al. Arctic Ocean warming contributes to reduced polar ice cap //J- Phys. Oceanogr. 2010. N 40. P. 2743-2756. doi: 10.1175/2010JP04339.1.

32. Rudels, B., Anderson L. G., and Jones E. P. Formation and evolution of the surface mixed layer and halocline of the Arctic Ocean //J. Geophvs. Res. 1996. N 101. P. 8807-8821.

33. Steele, M., and Boyd T. Retreat of the cold halocline layer in the Arctic Ocean //J. Geophvs. Res. 1998. N 103. P. 10 419-10 435.

34. Romanovskii N. N., Hubberten H. W., Gavrilov A. V., Eliseeva A. A., Tipenko G. S. Offshore permafrost and gas hydrate stability zone on the shelf of East Siberian Seas // Geo-Mar. Lett. 2005. V. 25. P. 167-182.

35. Eliseev A. V., Malakhova V. V., Arzhanov M. M., Golubeva E. N., Denisov S. N., Mokhov I. I. Changes in the boundaries of the permafrost layer and the methane hydrate stability zone on the Eurasian Arctic shelf, 1950-2010 // Dokladv Earth Sciences. December 2015. Volume 465, Issue 2, P. 1283-1288, doi: 10.1134/S1028334X15120107

36. Yurganov, L. N., Leifer I., LundMvhre C. Seasonal and interannual variability of atmospheric methane over Arctic Ocean from satellite data // Modern problems of remote sensing of the earth from space (Sovremennve problem distancionnogo zondirovanija zemli iz kosmosa). 2016. V. 13. N 2. P. 107-119,doi: 10.21046/2070-7401-2016-13-2-107-119.

37. Malakhova V. V., Golubeva Е. N. Assessment of the permafrost stability on the shelf of the Eastern Arctic under the extreme warming scenario in the XXI century // Lbdisneg. 2016. V. 56. N 1. P. 61-72.

38. Davies J. H. Global map of Solid Earth surface heat flow // Geochem. Geophvst. Geosvst. 2013. V. 14. N 10. P. 4608-4622.

39. Malakhova V. V., Golubeva E. N. On possible methane emissions from the East Arctic Seas // Atmosphere and Ocean Optics (Optika Atmosferv i Okeana). 2013. V. 26. N 6. P. 452-458.

40. Malakhova V. V., Eliseev A. V. Influence of rift zones and thermokarst lakes on the formation of subaqueous permafrost and the stability zone of methane hydrates of the Laptev Sea shelf in the Pleistocene // Lbdisneg. 2018. V. 58. N 2. P. 231-242.

41. Drijus M. R. Hydrothermal mode of reservoirs-coolers. Vilnius: Mokclas, 1985.

42. Terms of use of water resources of the Belovo reservoir / Prostrov-100 LLC. Moscow, 2001.

43. Kazmin S. P., Klimov О. V. Morphometric features of the Belovo reservoir and environmental assessment of the adjacent territory // Geo-Siberia-2011. Proc. VII International scientific cong. Novosibirsk, 2011. V. 4. P. 217-221.

44. Golubeva E. N., Platov G. A. On improving the simulation of Atlantic Water circulation in the Arctic Ocean // J. Geophvs. Res. 2007. V. 112. C04S05. doi:10.1029/2006JC003734.

45. Golubeva E. N. Numerical modeling of the dynamics of Atlantic waters in the Arctic basin using the QUICKEST scheme // Computational Technologies (Vvchislitelnve tekhnologii). 2008. V. 13. N 5. P. 11-24.

46. Kraineva M. V., Golubeva E. N., Lezhenin A. A., Klimov О. V. Study of the hydrothermal regime of the reservoir-cooler of the Belovo State District Power Plant using a numerical model // InterExpoGeo-Siberia. 2017. V. 4. N 1. P. 106-110.

47. Voevodin A. F., Nikiforovskava V. S., Ovcharova A. S. Numerical methods for solving the problem of unsteady water movement in the estuaries of rivers // Proceedings of AARI. 1983. V. 378. P. 23-34.

48. Krylova A. I., Antipova E. A. CHislennoe modelirovanie gidrologicheskogo rezhima v delte reki Lenv // Atmosphere and Ocean Optics (Optika Atmosferv I Okeana). 2018. V. 31. N 6. doi: 10.15372/A0020180600.

49. Korets M. A., Ryzhkova V. A., Danilova I. V. GIS-based approaches to assessment of the terrestrial ecosystems state in the Norilsk industrial area // Siberian ecological journal (Sibirskiv ekologicheskiv zhurnal). 2014. N 6. P. 887-902.

50. Savchenko V. A. Ecological Problems of the Taimyr. Moscow, 1998.

51. Shlvchkov V. A., Malbakhov V. M., Lezhenin A. A. Numerical modeling of atmospheric circulation and transport of contaminants in the Norilsk Valley // Atmosphere and Ocean Optics (Optika Atmosferv I Okeana). 2005. V. 18. N 5-6. P. 490-496.

52. Lezhenin A. A., Raputa V. F., Yaroslavtseva T. V. Numerical analysis of atmospheric circulation and pollution transport in vicinity of the Norilsk industrial region // Atmosphere and Ocean Optics (Optika Atmosferv I Okeana). 2016. V. 29. N 6. P. 467-471.

53. Kharuk V. I., Winterberger K., Tsibulskiv G. M., Yakhimovich A. P. Analysis of the technogenic degradation of tundra forests from space imagery // Exploration of the Earth from space (Issledovanie Zemli iz kosmosa). 1995. N 4. P. 91-97.

54. Igamberdiev V. M., Tereshenkov О. M., Kutvev Kh. A., Popova E. N. Assessment of the current state of the environment: Norilsk industrial region // National economy of the Komi Republic (Narodnoe khozvavstvo respubliki Komi). Syktyvkar. 1994. V. 3. P. 54-61.

55. Obolkin V. A., Potemkin V. L., Makukhin V. L., Chipanina Y. V., Marinavte I. I. Low-level atmospheric jets as main mechanism of long-range transport of power plant plumes in the Lake Baikal Region // Int. J. Environ. Studies. 2014. Vol. 71 (3). P. 391-397.

56. Lezhenin A. A., Yaroslavtseva Т. V., Raputa V. F. Using satellite information on smoke torch trajectories to calculate wind fields // InterExpoGeo-Siberia-2016. 2016. V. 1. P. 63-67.

57. Braun R. A. Analytical methods for modeling the planetary boundary layer //Leningrad, Gidrometeoizdat, 1978.

58. Raputa V. F., Shlvchkov V. A., Lezhenin A. A., Romanov A. N., Yaroslavtseva T. V. Numerical analysis of aerosol substance fallout from a high-altitude source // Atmosphere and Ocean Optics (Optika Atmosferv I Okeana). 2014. V. 27. N 8. P. 713-718.

Bibliographic reference: Platov G.A., Raputa V.F., Krupchatnikov V.N., Golubeva E.N., Malakhova V. V., Lezhenin A. A., Borovko I. V., Krylova A. I., Iakshina D. F., Krayneva M. V., Kravchenko V. V., Korobov 0. A. Creation and development of a multicomponent complex of models of the Earth hydrodynamic processes //journal “Problems of informatics”. 2019, № 2. P. 4-35. DOI: 10.24411/2073-0667-2019-00005

article

Snytnikova T. V.

Institute of Computational Mathematics and Mathematical Geophysics SB RAS,630090, Novosibirsk, Russia

EVOLUTION OF ASSOCIATIVE PARALLEL ARCHITECTURES

UDK 004.272

The hardware currently in use is primarily targeted to address data processing. But the Von Neiman’s architecture is not the only architecture type. The paper presents an overview of associative (content-addressable) parallel architectures from the first industrial associative processor STARAN to the modern ATLAS Fast TracKer. Such an architecture performs data parallelism at the basic level, provides massively parallel search by contents, and allows one using two-dimensional tables as basic data structures. However, to solve tasks on these systems, it is necessary to construct new approaches and methods which take into account the advantages of this architecture. Programming paradigms for associative parallel computers was formulated by Potter. The key paradigm of associative processors is the constant runtime of the logical and arithmetic data array operations.

The first commercially successful version of associative parallel processor was STARAN (Stellar Attitude Reference and Navigation ). It was developed by Goodyear Aerospace and produced in 1972. An associative processor array consists of 256 1-bit processor elements, a matrix memory, and a flip network. The matrix memory contains 256 words 256 bits long. Flip net allows one to move data between PE in parallel. Up to 32 associative processor arrays are connected to the one control logic unit, which is connected to host. The next associative system ASPRO (Airborne Associative Processor) was developed on the STARAN base in 1982. The ASPRO was used in US air traffic control system.

After that, in 1991, a parallel associative processor IXM2 was developed for ETL (ElectroTechnical Laboratory, Japan) for processing knowledge and for processing semantic networks. The IXM2 contains 64 associative processors and 9 network processors for communications. Eight associative processors and one network processor form a processing module. All associative processors in a processing module are completely interconnected each other and are connected to one network processor. And eight processing moduls are also completely interconnected each other and are connected to one network processor, which has the connection with the host. The IXM2 was used in the computer translating systems ASTRAL and EBMT (Example-Based Machine Translation) and the real time oral speech translating system TDMT (Transfer-Driven Machine Translation).

The next system, Rudger’s CAM2000 was developed at Rutgers University with the support of NASA in 1993. It combines the capabilities of an associative processor, an association memory and dynamic random access memory in the crystal. The CAM2000 architecture is a tree connected machine consisting of four pairwise connected components: a tree, a leaf, a memory, and input/output devices. A tree component consists of three tree-cells connected in the form of a binary tree. They perform global operations on data located in leaf-cells. A leaf-cell consists of a processor, a bank of local registers, a local memory, and one parallel shift register that forms the I/O components. Leaf-cells perform local operations on data located in their memory and in a variety of registers.

The last reviewed system is ATLAS Fast Tracker (FTK) System of Large Hadron Collider. The FTK system was designed as part of the detector ATLAS, designed to research the processes with high-energy particles as Higgs bason. So, the tracking system should provide the run-time processing of huge data ( about 1PB per second, and 109 matching per each 10-9 seconds) with restrictions on space and power consumption. The FTK system includes 128 independent associative processors AMBSLP (summary 8192 AMchips and more then 2000 FPGA).

The ATLAS FastTracKer is planned to make suitable for portable devices. And the FastTracKer may be useful to solve problems of high-energy physics, medical imaging, and research the visual functions of the brain. So, each of the considered associative parallel architectures was built to solve specific problems that could not be effectively solved on the systems of another architecture. Associative parallel computing developes in three directions: new hardware (associative memory chips, associativ processors and systems), associative parallel models and associative parallel algorithms, the implementation of associative models on existing hardware.

Key words: associative parallel arcitectures, SIMD, IXM2, Rutgers CAM2000, ATLAS FTK.

References

1. Krikelis A., Weems С. C.. Associative processing and processors // Computer. 1994. 27(11). P. 12-17.

2. Pagiamtzis K., Sheikholeslami A. Content-addressable memory (cam) circuits and architectures: a tutorial and survey // IEEE Journal of Solid-State Circuits. 2006. 41(3). P. 712-727.

3. Kocak T., Basci F. A power-efficient team architecture for network forwarding tables // Journal of Systems Architecture. 2006. 52(5). P. 307 — 314.

4. Noda H., Inoue K., Kuroiwa M. and el. A cost-efficient high-performance dynamic TCAM with pipelined hierarchical searching and shift redundancy architecture // IEEE Journal of Solid-State Circuits. 2005. 40: P. 245-253.

5. Potter J. L. Associative Computing: A Programming Paradigm for Massively Parallel Computers / Perseus Publishing, 1991.

6. Jalaleddine S. M. Associative memories and processors: The exact match paradigm // Journal of King Saud University — Computer and Information Sciences. 1999. ll(Supplement С). P. 45-67.

7. GOST 15971-90. Sistemv obrabotki informatsii. Terminv i opredeleniva [Information processing systems. Terms and Definitions]. 1991. P. 4.

8. Clements A. The Principles of Computer Hardware / Oxford University Press, 2000.

9. Tanenbaum A. S. Structured Computer Organization / Prentice Hall PTR, 1998.

10. Rudolph J. A. A production implementation of an associative array processor: Staran. In Proceedings of the December 5-7, 1972, Fall Joint Computer Conference, Part I, AFIPS ’72 (Fall, part I), New York, NY, USA, 1972. АСМ. P. 229-241.

11. Foster С. C. Content addressable parallel processors / Caxton C. Foster / Van Nostrand Reinhold New York, 1976.

12. Batcher К. E. Design of a massively parallel processor // IEEE Transactions on Computers. 1980. 29(9). P. 836-840.

13. Batcher К. E. Staran parallel processor system hardware //In Proceedings of the May 6-10, 1974, National Computer Conference and Exposition, AFIPS ’74. New York, NY, USA, 1974. ACM. P. 405-410.

14. GER-15637A. STARAN S APPLE Programming Manual / GOODYEAR AEROSPACE CORPORATION, OHIO. 1973.

15. Davis E. W. Staran parallel processor system software // Proceedings of the May 6-10, 1974, National Computer Conference and Exposition, AFIPS ’74, New York, NY, USA, 1974. АСМ. P. 17-22.

16. Batcher К. E. Bit-serial parallel processing systems // IEEE Transactions on Computers. 1982. 31(5). P 377-384.

17. Uhr L. M. Algorithm-Structured Computer Arrays and Networks: Architectures and Processes for Images, Precepts, Models, Information / Academic Press, Inc., Orlando, FL, USA, 1984.

18. Wang H., Walker R. A. Implementing a scalable asc processor / Parallel and Distributed Processing Symposium, 2003. Proceedings. International. 2003.

19. Mingxian J. Associative operations from masc to GPU // PDPTA’15 — The 21st International Conference on Parallel and Distributed Processing Techniques and Applications. Las Vegas: CSREA Press, 2015. P. 388-393.

20. Snvtnikova T. V., Snvtnikov A. V. Implementation of the star-machine on GPU // NCC Bulletin. 2016. 39. P. 51-60. '

21. Snvtnikova T. V., Nepomniaschava A. Sh. Solution of Graph Problems by Means of the StarMachine being implemented on GPUs // Prikladnava Diskretnava Matematika. 2016. 3(33). P. 98-115.

22. Higuchi T., Kitano H., Furuva T., Handa K., Kokubu A., Takahashi N. Ixm2: A parallel associative processor for knowledge processing //In Thomas L. Dean and Kathleen McKeown, editors, AAAI. AAAI Press / The MIT Press. 1991. P. 296-303.

23. Higuchi T., Furuva T., Handa K., Takahashi N., Nishivama H., Kokubu A. Ixm2: A parallel associative processor //In Proceedings of the 18th Annual International Symposium on Computer Architecture, ISCA ’91, New York, NY, USA, 1991. АСМ. P. 22-31.

24. Higuchi T., Furuva T., Handa K., Kokubu A. Initial evaluation of a parallel associative processor IXM2 // Microprocessing and Microprogramming. 1991. 31(1). P. 89 — 92.

25. Kitano H. Chapter ASTRAL: An Implementation on the IXM2 Associative Memory Processor / Speech-to-Speech Translation: A Massively Parallel Memory-Based Approach. Springer US, Boston, MA, 1994. P. 135-155.

26. Kitano H., Higuchi T., Tomita M. Massively parallel spoken language processing using a parallel associative processor IXM2 // The First International Conference on Spoken Language Processing, ICSLP 1990, Kobe, Japan. 1990. P. 917-920.

27. Oi K., Sumita E., Furuse O., Iida H., Higuchi T. Real-time spoken language translation using associative processors // Proceedings of the Fourth Conference on Applied Natural Language Processing. Stroudsburg, PA, USA, 1994., ANLC’94. P. 101-106.

28. Smith D. E., Hall J. S., Miyake K. Rutger’s CAM2000 Chip Architecture / Rutgers University, Department of Computer Science, Laboratory for Computer Science Research, 1993.

29. Smith D. E., Hall J. S., Miyake K. Rutger’s cam2000 chip architecture. Technical report, 1993.

30. Hsu С. H., Smith D. E., Levy S. Linear-C: A data-parallel extension to C / Technical Report LCSR-TR-273, Computer Science Department, Rutgers University, 1996.

31. Volpi G. Associative memory computing power and its simulation / Technical Report ATL- DAQ-PROC-2014-018, CERN, Geneva.2014.

32. Annovi A., Beretta M., Bossini E., Crescioli F., Dell’Orso M., Giannetti P., Piendibene M., Sacco I., Sartori L., Tripiccione R. Associative memory design for the fasttrack processor (ftk) at atlas. // Real Time Conference (RT). 2010. 17th IEEE-NPSS. P. 1-3.

33. The ATLAS Collaboration. The atlas experiment at the cern large hadron collider // Journal of Instrumentation. 2008. 3(08). P. S08003.

34. The ATLAS Collaboration. Expected performance of the ATLAS experiment: detector, trigger and physics. CERN, Geneva, 2009.

35. Cho A. The discovery of the higgs boson // Science. 2012. 338(6114). P 1524-1525.

36. Maznas I. Ftk: The hardware fast tracker of the atlas experiment at CERN // EPJ Web Conf. 2017. 137. P. 12001.

37. Biesuz N., Citraro S., Donati S., et al. Highly parallelized pattern matching execution for ATLAS event real time reconstruction // IEEE Transactions on Nuclear Science (TNS). 2016. 63. P. 1147-1154.

38. Pagiamtzis K., Sheikholeslami A. Content-addressable memory (CAM) circuits and architectures: A tutorial and survey. IEEE Journal of Solid-State Circuits. 2006. 41(3). P. 712-727.

39. Dell’Orso M., Ristori L. VLSI structures track finding // Nucl. Instr, and Meth. A. 1989. 278. P. 436-440.

40. Wissing Ch., Baird A., Baldinger R., et al. Performance of the hl fast track trigger: Operation and commissioning results // Proceedings of the 14th IEEE-NPSS Conference on Real Time, RTC’05, Washington, DC, USA, 2005. IEEE Computer Society, P. 233-236.

41. Bardi A., et al. The CDF online silicon vertex tracker // Nucl. Instrum. Meth.. 2002. A485. P. 178-182.

42. Annovi A., Bardi A., Bitossi M., et al. A VLSI processor for Fast Track finding based on content addressable memories // IEEE Transactions on Nuclear Science. 2006. 53(4). P 2428-2433.

43. Masi S. Periodic report summary 1 — FTK (Fast Tracker for Hadron Collider experiments) // Technical Report 324318, Industry-Academia Partnerships and Pathways, Italy. 2015.

44. Asbah N. A hardware fast tracker for the ATLAS trigger // Physics of Particles and Nuclei Letters. 2016. 13(5). P. 527-531.

45. Maznas I. FTK: The hardware Fast TracKer of the ATLAS experiment at CERN // Technical Report ATL-DAQ-PROC-2016-033, CERN, Geneva. 2016.

46. Sotiropoulou C. L., Gkaitatzis S., Annovi A., et al. A Multi-Core FPGA-Based 2D-Clustering Implementation for Real-Time Image Processing // IEEE Trans. Nucl. Sci. 2014. 61(6). P. 3599-3606.

47. Okumura Y., Liu T., Olsen J., et al. Atca-based atlas FTK input interface system // Journal of Instrumentation. 2015. 10(04). P. C04032.

48. Ng K.F., and Rochester Institute of Technology. Computer Engineering. / Novel Low Power CAM Architecture. Rochester Institute of Technology, 2008.

49. Xu W., Zhang T., and Yiran Chen Y. Design of spin-torque transfer magnetoresistive RAM and CAM TCAM with high sensing and search speed // IEEE Transactions on Very Large Scale Integration (VLSI) Systems. 2010. 18(1). P. 66-74.

50. Imani M., Rahimi A., Rosing T. S. Resistive configurable associative memory for approximate computing / 2016 Design, Automation Test in Europe Conference Exhibition (DATE).2016. P. 13271332.

51. Stempkovskiv A. L., Klimov A. V., Levchenko N. N., Okunev A. S. Metodv adaptatsii parallelnov potokovov vvchislitelnov sistemv pod zadachi otdelnvh klassov // Informatsionnve Tehnologii i Vvchislitelnve Sistemv. 2009. 3. P. 12-21.

52. Zmeev D. N. Sredstva proektirovaniva vvsokoproizvoditelnvh potokovvh vvchislitelnvh sistem // Problemy Razrabotki Perspektivnyh Mikro- i Nanoelectronnyh sistem (MES). 2016. 2. P. 159-163

Bibliographic reference: Snytnikova T. V. Evolution of associative parallel architectures //journal “Problems of informatics”. 2019, № 2. P. 36-50. DOI: 10.24411/2073-0667-2019-00006

article

Azhbakov A.A., Perepelkin* V.A.

Novosibirsk State University, 630090, Novosibirsk, Russian Federation,

*Institute of Computational Mathematics and Mathematical Geophysics SB RAS,630090, Novosibirsk, Russian Federation

DEVELOPMENT AND IMPLEMENTATION OF DISTRIBUTED PORTABLE ALGORITHMS OF FRAGMENTED PROGRAMS EXECUTION ON HETEROGENEOUS MULTICOMPUTERS

UDK 004.4'23

Parallel programming automation in numerical computations demands development of effective distributed system algorithms, capable of efficient execution of parallel programs, represented in high-level programming languages. This, in turn, demands conduction of many efficiency tests and experiments for a variety of applications and multicomputers. Of special importance are heterogeneous multicomputers, which comprise computing nodes of various configurations, connected by networks of different capabilities, since high performance computers tend to increase their heterogeneity, as well as different multicomputers tend to join into larger heterogeneous multicomputers. Nowadays there are many possibilities to aggregate various devices (such as cluster nodes, servers, personal computers, tablets and smartphones) into a single highly heterogeneous multicomputer, but there is a lack of software, suitable for conducting numerical computations on such multicomputers with an ability to vary system algorithms.

In the paper a distributed run-time environment is introduced, which is capable of execution of distributed parallel programs, written in LuNA language, on such highly heterogeneous hardware. To achieve good portability web-technologies were employed. Also, the architecture of the runtime environment supports replacement of the most of system algorithms, responsible for resources distribution, static and dynamic load balancing, computations scheduling, garbage collection, network routing etc. Thus, the environment is suitable for studying different system algorithms on highly heterogeneous multicomputers. The LuNA (Language for Numerical Algorithms) language was chosen as the basis because of the computational model, employed in the language. This model (called fragmented algorithm) allows defining computations in a portable, hardware-independent way, without pre-defined resources distribution or computations schedule. Fragmented algorithm represents computations as a set of side-effect-free micro-processes called computational fragments, which process immutable pieces of data called data fragments. In order to execute a fragmented algorithm the runtime environment has to assign fragments to computing nodes and deliver data fragments to their consumers — computational fragments. The problem of fragmented algorithm efficient execution is solved separately from the „numerical" part of computations. The run-time environment developed is compatible with LuNA compiler (i. e. it executes LuNA-program internal representation, produced by LuNA compiler).

The run-time environment developed focuses on portability, parameterization and scalability. Portability is necessary to allow usage of wide specter of computing nodes (and, thus, support a variety of heterogeneous multicomputers). Parametrization means the ability to replace various system algorithms with user-provided ones in order to study them in the field. Scalability is implied by large- scale numerical computations, where no centralized algorithms, communications or data structures are allowed unless demanded by the application.

The paper proposes an analysis of fragmented algorithm execution in order to identify system algorithms, which are needed to cover the problem of efficient fragmented algorithm execution. According to the analysis architecture of the run-time environment is proposed, which provides necessary parametrization and scalability. For portability concerns the run-time environment was implemented in JavaScript and can be run in virtually any web-browser or under the Node.JS platform. All run-time environment instances form a peer-to-peer network using the Web Sockets technology. The topology of the network can also be controlled by a user module.

Some preliminary testing was conducted. A model problem was studied on a number of multicomputer configurations. The configurations included different nodes: personal multicore computer under OS Windows, a multicore server under Linux, a notebook, and Android smartphones. The tests conducted showed identical output to the output, produced by the original LuNA run-time system. Comparative performance tests were also conducted, which showed the expected curves of different parallelization efficiencies for different computation volume to data volume ratios. Further research should include study of a number of real applications and different system algorithms.

Key words: fragmented programming technology fragmented programming system LuNA, webtechnologies.

References

1. Cloud Haskell. [Electron. Res.]: http://haskell-distributed.github.io/ (accessed: 01.04.2019).

2. Carlton M., Van Roy P. A distributed Prolog system with AND-parallelism // Proceedings of the Twenty-First Annual Hawaii International Conference on System Sciences. Volume II: Software track. 1988.

3. Kale, Laxmikant V. and Bhatele, Abhinav. Parallel Science and Engineering Applications: The Charm++ Approach. Taylor & Francis Group, CRC Press, 2013. ISBN 978-1-4665-0412-7

4. Bosilca, G., Bouteiller, A., Danalis, A., Faverge, M., Herault, T., Dongarra, J. PaRSEC: Exploiting Heterogeneity to Enhance Scalability // IEEE Computing in Science and Engineering. November, 2013. Vol. 15. N 6. P. 36-45.

5. X10 for High Performance Scientific Computing. Josh Milthorpe. Ph.D. Thesis, Research School of Computer Science, Australian National University, June 2015.

6. Treichler Sean, Bauer Michael, Sharma Rahul, Slaughter Elliott, and Aiken Alex. Dependent Partitioning //In Object Oriented Programming, Systems, Languages, and Applications (OOPSLA 2016).

7. Malvshkin Victor E., Perepelkin Vladislav A. LuNA Fragmented Programming System, Main Functions and Peculiarities of Run-Time Subsystem // Parallel Computing Technologies. 11th International Conference, PaCT 2011, Proceedings. LNCS 6873. Springer, 2011. P. 53-61.

8. Malvshkin. V., Perepelkin. V., Schukin G. Scalable Distributed Data Allocation in LuNA Fragmented Programming System // Journal of Supercomputing, S.I.: Parallel Computing Technologies - 2016. Springer, 2016. P. 1-7. DOI: 10.1007/sll227-016-1781-0.

9. Boost C++ Libraries. [Electron. Res.]: https://www.boost.org/ (accessed: 01.04.2019)

10. Message Passing Interface (MPI) Forum. [Electron. Res.]: https://www.mpi-forum.org/ (accessed: 01.04.2019).

11. Javascript performance benchmarks. [Electron. Res.]: https://benchmarksgame-team.pages, debian.net/benchmarksgame/faster/j avascript.html (accessed: 01.04.2019).

Bibliographic reference: Azhbakov A. A.. Perepelkin V. A. Development and implementation of distributed portable algorithms of fragmented programs execution on heterogeneous multicomputers //journal “Problems of informatics”. 2019, № 2. P. 51-69. DOI: 10.24411/2073-0667-2019-00007

article

Main menu

You are here

2019 № 2(43)

Languages