A parallel data-structure for modular programming of triangulated computing media.
Tóm tắt
Our long-term project involves performing general-purpose computation on 2D amorphous computing media, which consist of arbitrary many, small, identical processing elements that are homogeneously spread in 2D Euclidian space, and that communicate locally in space. While the minimal assumptions on hardware provide the fascinating perspective of arbitrary large computing power, they also make programming notoriously difficult. Furthermore, our project involves simulating objects extended in 2D-space, called “blobs”. Maintaining the connectedness of blobs while they move in space adds another layer of difficulty since it demands to process the topology of 2D space. This paper describes a new parallel data structure that can simplify the programming task, in this context. In computer graphics, processing related to 2D topology is performed by using triangle meshes. We consider synchronous media whose underlying network is also a triangle mesh. Our data structure, derived from computer graphics, is anchored on that mesh so that its operations can be compiled on the medium. More precisely, our compiler produces a circuit of logic gates, which enables a high-performance simulation, in the case of crystalline media (Cellular Automata). We demonstrate the expressiveness of the data structure’s operation by using an incremental and modular programming style. We program, first small, then larger building-block functions, and re-use them. Blobs are implemented and re-used to compute the Voronoï diagram. What is the scope of the data-structure? This poses the question of whether there exists a universal set of primitives able to program any processing specified only in terms of 2D-geometry.
Tài liệu tham khảo
Abelson H, Allen D, Coore D, Hanson C, Homsy G, T. F, Knight J, Nagpal R, Rauch E, Sussman GJ, Weiss R, (2000) Amorphous computing. Commun ACM 43(5):74–82
Adamatzky A (1996) Voronoi-like partition of lattice in cellular automata. Math Comput Model 23(4):51–66
Audrito G, Viroli M, Damiani F, Pianini D, Beal J (2019) A higher-order calculus of computational fields. ACM Trans Comput Log (TOCL) 20(1):1–55
Beal J, Dulman S, Usbeck K, Viroli M, Correll N(2013) Organizing the aggregate: languages for spatial computing. In: Formal and practical aspects of domain-specific languages: recent developments, IGI Global, pp. 436–501
Beal J, Pianini D, Viroli M (2015) Aggregate programming for the internet of things. Computer 48(9):22–30
Bhattacharjee K, Naskar N, Roy S, Das S (2020) A survey of cellular automata: types, dynamics, non-uniformity and applications. Nat Comput 19(2):433–461
Chopard B, Droz M(1998) Cellular automata modeling of physical systems. 01
Coore D(1999) Botanical computing: a developmental approach to generating interconnect topologies on an amorphous computer. Ph.D. thesis, MIT
Gruau F(2018) Video illustrating the medium for self developing network. https://youtu.be/8yVkfD0_G9s or https://www.lri.fr/ \(\sim\)gruau/\(\#\)development
Gruau F, Eisenbeis C, Maignan L(2008) The foundation of self-developing blob machines for spatial computing. phys D Nonlinear Phenom 237
Gruau F, Maignan L(2018) Spatial types: a scheme for specifying complex cellular automata to explore artificial physics. In: TPNC 2018. LNCS, vol. v, p. pp
Gruau F, Malbos P(2002) The blob: a basic topological concept for hardware-free distributed computation. In: UMC 2002. LNCS, vol. 2509, pp. 151–163
Kahn J.M, Katz R.H, Pister K.S(1999) Next century challenges: mobile networking for “smart dust”. In: Proceedings of the 5th annual ACM/IEEE international conference on mobile computing and networking. pp. 271–278
Maignan L, Gruau F(2008) Integer gradient for cellular automata: principle and examples. In: SASO 2008, IEEE
Maignan L, Gruau F(2009) A 1D cellular automaton that moves particles until regular spatial placement. Parallel Process Lett 19(2): 315–331, http://dx.doi.org/10.1142/S0129626409000249
Maignan L, Gruau F(2011) Gabriel graphs in arbitrary metric space and their cellular automaton for many grids. ACM Trans Auton Adapt Syst 6(12:1)–12:14. https://doi.org/10.1145/1968513.1968515,
Maignan L, Gruau F(2010) Convex hulls on cellular automata. In: Proceedings of the 9th international conference on Cellular automata for research and industry. ACRI’10, Springer-Verlag, Berlin, Heidelberg , pp 69–78. http://dl.acm.org/citation.cfm?id=1927432.1927440
Maniatty WA, Szymanski BK (1997) Fine-grain discrete voronoi diagram algorithms in l1 and l\(\infty\) norms. Math Comput Model 26(4):71–78
Rauch E (2003) Discrete amorphous physical models. Int J Theoret Phys 42(2):329–348
Schlömer T, Heck D, Deussen O(2011) Farthest-point optimized point sets with maximized minimum distance. In: Proceedings of the ACM SIGGRAPH
Toffoli T, Bach T(2001) A common language for “programmable matter” (cellular automata and all that). Bull It Assoc Artif Intell 14(2): 187–201, http://pm1.bu.edu/~tt/publ/aiia.ps.gz
Toffoli T, Margolus NH (1990) Invertible cellular automata: a review. Phys D Nonlinear Phenom 45(1–3):229–253
Van Kreveld M, Schwarzkopf O, deBerg M, Overmars M(2000) Computational geometry algorithms and applications. Springer
Wolfram S (1983) Statistical mechanics of cellular automata. Rev Mod Phys 55(3):601–644
Zhou H, Jin M, Wu H(2013) A distributed delaunay triangulation algorithm based on centroidal voronoi tessellation for wireless sensor networks. In: MobiHoc ’13. ACM