Lecture 13: Two-Norm, PageRank, Lambda¶

Two-norm¶

We first take a look how to parallel the Two Norm task using std::async. Here we create a PartitionedVector class to partition the index space of the vector explicitly among different tasks.

Next we implement Two Norm using PartitionedVector class by passing a portion of the vector to std::async. However, the first version we implement has a hidden issue. Specifically, we examine how std::async handles the arguments that it handles. To avoid the overhead of copying in out Two Norm example, we have to explicitly tell std::async to pass the vector by reference with the help of std::ref(). Based on this observation, we propose our improved Two Norm version.

Lambda¶

We also introduce Lambda in this lecture.

Anonymous function or lambda function or lambda is a function definition that is not bound to an identifier. It is invented by Alonzo Church in 1936. It became a feature in Lisp programming language in 1958. Nowadays, it has been supported by more and more modern programming languages. It was added to C++ since C++11.

Below is a lambda definition of our partial_pi function.

Based on this lambda definition, we rewrite our program to approximate the value of pi. However, we notice that we are passing index k, blocksize, and h all as parameters in our lambda. Why cannot we use k, blocksize, and h directly? To accommodate this, lambda provides capture clauses which allow lambda to capture variable by value or by reference.

Short excursus on Lambda can be accessed at More on Lambda.

PageRank¶

Finally, our second case study is PageRank. PageRank is an algorithm to rank web pages on Internet used by Google Search. Assuming a person is surfing on Internet, it is nothing but a random walk on the web graph. Here the web graph consists of the websites as the vertices or nodes, and the links as the edges.

The simplified PageRank algorithm uses the Power Method to compute the rankings of the websites. Its essence is the matrix-vector product. Because there are cycles on the web graph. Once we get into this cycle we can’t get out . Therefore, PageRank has to include this “teleportation” to avoid this situation. Because there is a small probability that users might go from a site to any other site (teleportation) in the web graph, we implement a basic PageRank with teleportation bias using our two_norm function we studied earlier in this lecture.