L3 Bitonic Sequences

直接看中文的吧：
https://blog.csdn.net/Asensio_20/article/details/105068977

L4 Scans and List Ranking

介绍三个算法：

Scan

The generalization of a prefix operation is called a scan.
For example: sumscan,productscan,maxscan,etc.
Parallel scans require iterations of the loop to be independent of one another.
Prefix-sum 的算法可以参考：
https://baimafujinji.blog.csdn.net/article/details/6477724

Parallel QuickSort

普通快排多线程为什么不能并行？因为放置数据的队列长度是有依赖关系，因此不能并行。
可以利用 scan 的思想来进行优化：
To do the quicksort in parallel →

1. Select a pivot .
2. In parallel → compare each element to the pivot. If the element is less than or equal to the pivot put a ‘1’ in the auxiliary array . If the element is greater than put a ‘0’ in the auxiliary array. This will result in a array consisting of 1s and 0s. This array can be scanned. The following information can be gotten from the scan:
3. The last element in the array is the total number of elements less than or equal to the pivot . This means we can allocate an output array of the appropriate size.
4. Every time there is an increase in the scan, this corresponds to an element in the array that is less than or equal to the pivot. This makes the desired elements easy to find in a scan.
5. Within the scan the incremental values are both unique and consecutive . These values can be used as indices to the output array and can be written in parallel. 上面的 5 个步骤都不依赖于前面的结果，所以是可以并行的。 W(n) = O(n) D(n) = O(log n)

List Ranking

List ranking asks:
Given a linked list what is the distance of each node from the head?（虽然我个人觉得这个在实际中好像没啥用，但是不妨碍理解一下算法。）

1. store the list as an array pool A linked list has only one entry point, to make it more accessible, use two arrays. One array will hold the value of the node, the second array will hold the index (the next pointer) . The array representation must be at least as large as the linked list. 需要保证两个 Array pool 长度大于 list 的长度。其中一个放入对应节点的数值，另一个放入后继节点的 index.

2. List ranking is basically an addscan
   
   Candidate invariant: if 1s are used to denote rank, the jumps will disturb this method. So the
   ranking should be changed to be an addscan add
   the ranks and store this in the array.
   
   

3. Use the jump primitive to divide and conquer.
   To make this parallel, use the jump primitive.
   The jump primitive → takes a nodes pointer (that was pointing to the neighbor) and points it to
   the neighbors neighbor.
   

   NEXT:

NEXT:

NEXT:

伪代码：

很晕，很晕。。。