We introduce a set of state access patterns suitable for managing accesses to states in parallel computations operating on streams. The state access patterns are useful for modelling typical stream parallel applications. We present a classification of the patterns according to the extent and way in which the state can be structured and accessed. We define precisely the state access patterns and discuss possible implementation schemas, performances and possibilities to manage adaptivity (parallelism degree) in the patterns. We present experimental results relative to implementations built on top of the structured parallel programming framework FastFlow that demonstrate the feasibility and efficiency of the proposed access patterns.
AndradeHCMGedikBTuragaDS (2014) Fundamentals of Stream Processing: Application Design, Systems, and Analytics. 1st ed.
New York: Cambridge University Press.
2.
AsanovicKBodikRDemmelJ. (2009) A view of the parallel computing landscape. Communications of the ACM52 (10): 56–67.
3.
ColeM (2004) Bringing skeletons out of the closet: A pragmatic manifesto for skeletal parallel programming. Parallel Computing30 (3): 389–406.
4.
DaneluttoMDeriLSensiDD. (2011) Network monitoring on multicores with algorithmic skeletons. In: Applications, tools and techniques on the road to exascale computing, proceedings of the conference ParCo 2011 (Advances in Parallel Computing, vol. 22), Ghent, Belgium31 August–3 September 2011, pp.519–526. IOS Press.
5.
DaneluttoMDeriDDe SensiD. (2014) Deep packet inspection on commodity hardware using fastflow. In: Parallel Computing: Accelerating Computational Science and Engineering (CSE) (Proceedings of PARCO 2013, Munich, Germany) (Advances in Parallel Computing, vol. 25). Munich: IOS Press, pp.92–99.
6.
DaneluttoMDe MatteisTMencagliG. (2016) Data stream processing via code annotations. The Journal of Supercomputing1–15. DOI: 10.1007/s11227-016-1793-9.
7.
DaneluttoMDe MatteisTDe SensiD. (2017) P3 ARSEC: Towards parallel patterns benchmarking. In: Proceedings of the 32th annual ACM symposium on applied computing, SAC ‘17, Marrakech, Morocco, 4–6 April 2017. New York: ACM.
8.
DaneluttoMTorquatiM (2015) Structured parallel programming with “core” fastflow. In: ZsókVHorváthZCsatóL (eds) Central European Functional Programming School (Lecture Notes in Computer Science, vol. 8606). Switzerland: Springer International Publishing, pp.29–75.
9.
De MatteisTMencagliG (2016) Keep calm and react with foresight: strategies for low-latency and energy-efficient elastic data stream processing. In: Proceedings of the 21st ACM SIGPLAN symposium on principles and practice of parallel programming (PPoPP ’16), Barcelona, Spain, 12–16 March 2016, pp.13:1–13:12. New York, NY, USA: ACM. DOI: 10.1145/2851141.2851148.
10.
del Rio AstorgaDDolzMFSanchezLM. (2016) Discovering pipeline parallel patterns in sequential legacy C++ codes. In: BalajiPLeungK-C (eds) Proceedings of the 7th international workshop on programming models and applications for multicores and manycores (PMAM’16), Barcelona, Spain, 12–16 March 2016, pp.11–19. New York, NY, USA: ACM. DOI: 10.1145/2883404.2883411.
11.
EnmyrenJKesslerCW (2010) Skepu: a multi-backend skeleton programming library for multi-GPU systems. In: Proceedings of the fourth international workshop on High-level parallel programming and applications (HLPP ’10), Baltimore, Maryland, USA, 25 September 2010, pp.5–14. New York, NY, USA: ACM. DOI: 10.1145/1863482.18 63487.
12.
ErnstingSKuchenH (2012) Algorithmic skeletons for multi-core, multi-gpu systems and clusters. International Journal of High Performance Computing and Networking7 (2): 129–138.
13.
FernandezRCMigliavaccaMKalyvianakiE. (2013) Integrating scale out and fault tolerance in stream processing using operator state management. In: Proceedings of the 2013 ACM SIGMOD international conference on management of data (SIGMOD ’13), New York, USA, 22–27 June 2013, pp.725–736. New York, NY, USA: ACM. DOI: 10.1145/2463676.2465282.
14.
GammaEHelmRJohnsonR. (1995) Design Patterns: Elements of Reusable Object-oriented Software. Boston: Addison-Wesley Longman Publishing Co., Inc.
15.
GedikB (2014) Partitioning functions for stateful data parallelism in stream processing. The VLDB Journal23 (4): 517–539.
16.
McCoolMReindersJRobisonA (2012) Structured Parallel Programming: Patterns for Efficient Computation. 1st ed.
San Francisco, CA: Morgan Kaufmann Publishers Inc.
PoldnerMKuchenH (2008) On implementing the farm skeleton. Parallel Processing Letters18 (1): 117–131.
19.
VerdúJNemirovskyMValeroM. (2008) Multilayer processing – an execution model for parallel stateful packet processing. In: Proceedings of the 4th ACM/IEEE symposium on architectures for networking and communications systems, ANCS ‘08, San Jose, California, 6–7 November 2008, pp.79–88. New York: ACM.
20.
WuSKumarVWuKL. (2012) Parallelizing stateful operators in a distributed stream processing system: How, should you and how much? In: Proceedings of the 6th ACM international conference on distributed event-based systems, DEBS ‘12, pp.278–289. New York: ACM.
