Playing with monoids and discovering for oneself how frequently they turn up in various guises and how much is expressed by them is a delight. Not only it brightens the day of important but frankly boring data analytics. Not only it challenges to discover efficient (with the constant time and space operation) monoids, which demands ingenuity. In the words of Guy Steele, inventing efficient associative combining operators is a very big deal. An efficient monoid opens up parallel implementations – not just parallel but embarrassingly parallel: The input sequence arbitrarily partitioned among workers, all running in parallel with no races, dependencies or even memory bank conflicts. This is the ideal for multi-core, GPU or distributed processing. In this paper we show why monoids are a big deal, and also a big fun – even more than expected. Horner rule and Boyer-Moore majority voting – commonly regarded as prototypically inherently sequential – turn out monoids, and hence embarrassingly parallelizable. As we generalize monoids to observable monoids, we discover a new, vertical way to combine them, enabling efficient iterated grouping and aggregation directly on raw deserialized (big) data, on multicore or multi-processor.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

More Fun with Monoids

  • Oleg Kiselyov

摘要

Playing with monoids and discovering for oneself how frequently they turn up in various guises and how much is expressed by them is a delight. Not only it brightens the day of important but frankly boring data analytics. Not only it challenges to discover efficient (with the constant time and space operation) monoids, which demands ingenuity. In the words of Guy Steele, inventing efficient associative combining operators is a very big deal. An efficient monoid opens up parallel implementations – not just parallel but embarrassingly parallel: The input sequence arbitrarily partitioned among workers, all running in parallel with no races, dependencies or even memory bank conflicts. This is the ideal for multi-core, GPU or distributed processing. In this paper we show why monoids are a big deal, and also a big fun – even more than expected. Horner rule and Boyer-Moore majority voting – commonly regarded as prototypically inherently sequential – turn out monoids, and hence embarrassingly parallelizable. As we generalize monoids to observable monoids, we discover a new, vertical way to combine them, enabling efficient iterated grouping and aggregation directly on raw deserialized (big) data, on multicore or multi-processor.