On Dense Liniar Algebra, Graph Algorithms, Monte Carlo

I must admit that before reading about OPL I was not at all familiar with computation patterns in general. After doing a bit of internet research I came to understand the following about computational patterns. They are not exactly design patterns. OPL’s structural design patterns for instance, define the structure of a system, without indicating what is actually computed. Computational patterns (dwarfs) however, embody the generalized idiom for parallelism used to implement these structural patterns. The analogy is with civil engineering, where structural patterns would describe a factory’s physical structure and general workflow while computational patterns describe the factory’s machinery, flow of resources, and work-products. As with OPL, structural and computational patterns can be combined in the “pattern language” to provide a template for architecting arbitrarily complex parallel software systems.

I expect that the Graph Algorithm Pattern must have been a straightforward read for everybody. Once the graph concepts are clear, most of the details of the first three steps recommend by the pattern are clear: recognizing the problem, determining the data structure, defining the temporary data structures to store traversal variables. Very similar challenges are to be faced with every sequential graph problem. However, I found particularly interesting the graph related aspects of parallelism scattered throughout the four steps. Since for many graph structures there is a limited number of parallelization opportunities, I think that this information is very important. For instance, based on knowledge graph theory, we can choose to eliminate some edges and scope the traversal operation into independent localized partitions such that the partitions can be solved in parallel. Each type of graph is presented in the paper with its specific parallelization opportunities.

Dense Linear Algebra Pattern also seems to be well written. I especially appreciated the figures in this pattern, which support the good understanding of the pattern applied to matrix multiplication. In the Monte Carlo description, one can also get a very good visual understanding of the pattern.

One difference I noticed in the Dense Linear Algebra Pattern compared with Graph Algorithm and Monte Carlo is the way in which the Solution section is structured. In comparison with the latter two patterns, which offer a formal guideline as a sequence of steps in which a particular problem should be approached, Dense Linear Algebra Pattern’s solution suggests the usage of linear algebra libraries or BLAS routines and templates. Finally, if no such library is available or the problem is too specialized, the pattern goes over details on how to structure computation in order to optimize utilization of the memory hierarchy. These are all valuable and interesting details however I am still missing a formal sequence of steps to tell me how to approach this type of problems. For instance, I would have expected something like: 1) recognize linear algebra operations to solve 2) figure out if linear algebra library is available and offers this particular operation 3) figure out whether structuring data to pass as input to library does not lead to potentially suboptimal algorithms 4) if that is the case implement yourself optimized operation using domain specific language.