An Adventurous Language-I

As I mentioned in my earlier post it is more than important to learn and learn well the German language for an eventful stay in Germany; the stay may still be eventfull in other case but may not be pleaseantly eventful. In the last semester (Summer 2008) I embarked on improving my German language skills. The journey (hard and fought) was two act play.

The initial attempt was non intensive, twice a week course. The class size was good for individual to ask questions and discuss and the environment was freindly enough. As the class progressed our ideas about the language started to evolve like a sine function, somoetimes we thought its that easy and other times it seems above our intellectual abilities to learn it. The later thought overpowered the initial thinking more frequently. The first time I feel that its hard when I learnt that there are three types of gender for classification of each noun. Unlike English where we use “the”, in the German we have three variations der – for masculine, die – for feminine and das – for neutral. But the problem is that it is not the actual noun (person or place) that has gender but infact the word that is used to represent that noun.For instance one common example that is used in this regard is that of car, its has two words Auto and Wagen, but the interesting thing is that auto is das Auto (neutral) and wagen is der Wagen (masculine). In addition it is also mandatory to capitilize noun, so if you ever happen to read a German transcript then do not confuse the capitalization of nouns with proper noun. The first exam happened to be total disastrous as I struggle to remember the articles (die der das) for nouns. Second exam was good as there were no more articles and we moved on to some more advance materials.

In August I took the second course, it was four week intensive course. This time our class was truly a global class, whole of the world was somehow represented. From far East Asia to Europe, Australia to South America and from Africa to United Sates; a blend of all cultures. As the language course was intensive so I got the opportunity to practice it more and slight improvement was also made. It was amazing to learn about the cultures and tradition of so many different nations and to know “How do we do that….” was good addition to experience. The claim that I improve my German can be substantiated on the fact that at the end of the course I was able to understand a German song . The song was quite simple and when hearing we were having the lyrics of the song so it was not that diffiult to understand what the singer was trying to convey. By the way the song title was “Willst du mit mir gehn?” The video is as below and the German lyrics are here and English translation can be found here.

Engineering a Cache Oblivious Sorting Algorithm

(The report below was submitted in my Seminar on Algorithm Engineering, the paper was written by Brodal et al. Here I have presented why do we need cache oblivious algorithms and description of the two important cache oblivious sorting algorithms i,e Funnel Sort and Lazy Funnel Sort  followed by improvement as suggested by the authors for implementation of Lazy Funnel Sort).

The pdf version of the document can be found here.

1.1 Algorithm Analysis:

One of the most important considerations in the design of the algorithm is the efficiency. There are three general ways to measure the efficiency of algorithms. These include experimental analysis, average case and worst case analysis. The last two approaches are purely theoretical and do not consider the real world scenarios and does not consider factors that may affect the running time of algorithm. But the advantage of theoretical analysis is that it analyzes the algorithm independent of the hardware architecture on which the algorithm will be implemented, thus providing an insight into running time of algorithm independent of the hardware architecture. Hence it becomes really difficult to rely on single model for algorithm complexity. So we have to rely on experimental results as well to gauge the effectiveness of the algorithm in real world scenario.

When we consider the actual running time of an algorithm, then the memory system of computer has significant effect on the running time. It means the memory access time plays an important role in overall running time of algorithm, the latency associated with transfer of data from higher level to lower level, for example from Hard Disk to RAM or from RAM to Cache. In order for the algorithm to perform better in real world scenario it has to minimize the latency involved. Though the CPU speed is increasing following the Moore’s Law (The number of transistor on single chip doubles every eighteen months) , the same performance increase in the RAM is not visible. As per a study [1] the increase in speed of CPU and RAM is 55% and 7% respectively per year and this results in wide CPU-RAM performance gap. The figure below illustrates the gap more illustratively:

Fig 1: CPU-RAM Performance Gap

For more precise analysis of algorithms, the computational models must consider the memory architecture and factors such as hierarchy of memory, latency etc. We will discuss the model later but before that we need to understand the memory hierarchy of simple computer.

1.2 Ideal Cache Model

Let us consider a simple computer with two level of memory hierarchy as shown in the figure 2 below:

Fig 2: A Simple Computer with Two Level of Memory Hierarchy

We assume that Main Memory (RAM) is of arbitrarily large size, cache is partitioned into small blocks called “Cache Line” and each cache line consists of “B” consecutive locations. Data from main memory to cache is transferred in form of blocks such that size of each block is “B”. The total size of cache is “M” so there can be a total of M/B cache lines. We work on assumption of tall cache, which means that M >B². A cache hit occurs whenever data referenced by CPU is present in the cache and if the data is not present in cache and it has to be fetched from main memory then it is referenced as cache miss. We also assume that there is an optimal offline strategy for cache line replacement.

As for as the complexity in ideal cache model is concerned, there are two approaches:

·         Work Complexity, W(n),  which is conventional running time in RAM

·         Cache Complexity, Q(n, M, B), the number of cache misses as function of M and B.

Where

                n = input size

1.3 Cache Aware Vs Cache Oblivious Algorithms

Cache Aware and Cache Oblivious Algorithms are two different attempts that have been made to reduce the gap between actual running and theoretical running time of algorithms. The cache aware algorithms are based on parameters that can be tuned to optimize the cache complexity, these algorithms have prior knowledge about the size of cache and block etc and in practice are designed to for two known level of memory hierarchy. This makes them sub optimal for other memory levels and they often do not perform well.

In contrast to Cache Aware algorithms, Cache Oblivious algorithms have no prior information about the hardware parameters like cache size etc.

1.3.1 Advantages of Cache Oblivious Algorithms:

• The algorithm performs significantly better even without having any prior information about characteristics of memory hierarchy.
  
• There is no need to hardwire the memory characteristics in algorithm.
  
• Optimizing algorithm for one unknown level optimizes it for all levels.
  
• Cache Oblivious Algorithms are more robust and portable and thus are useful for development of software libraries.
  

1.3.2 Design Technique for Cache Oblivious Algorithm

One of the main techniques used to design cache oblivious algorithm is Divide and Conquer [2]. As like in traditional divide and conquer approach, the problem is divided repeatedly into small problems till a base case is achieved. In cache oblivious algorithms base case is reached when the sub problem is easily solvable, that is the sub problem should not cause cache miss and should fit in cache.

1.4 Cache Oblivious Sorting Algorithms:

Sorting algorithm is one of the most comprehensively researched topic in classical computer science. Sorting is being used in many of the graph, geometric and scientific applications as sub-routine. This means that efficient sorting algorithms will obviously increase the efficiency of the whole application. There are several Cache Oblivious Sorting algorithms presented; most notable of them are Funnel Sort[3], Lazy Funnel Sort[4] and Distribution based sorting algorithm[3].

1.4.1 Funnel Sort

Funnel Sort was the first cache oblivious sorting algorithm presented by Frigo et al[3].  The asymptotic working complexity of funnel sort is O(nlogn) where as if tall cache assumption holds then cache complexity is O(N/B logM/BN/B). The K-Funnel form the basis for the Funnel Sort.

A K-Funnel merges K³ elements at single invocation and consists of √K funnels at bottom; each bottom funnel is connected to top funnel via √K buffers. Figure 3 shows a 16-funnel with 16 input streams.

Fig 3: A 16-funnel with 16 input streams

Funnel Sort is laid in memory via van Emde Boas (vEB) layout; it means that first top tree “R” is laid out in memory followed recursively by B₀, L₀, B₁  and so on. The buffer size (B₀, B₁, B₂, B₃) is double than that of the input streams to accommodate the output arising from there. For initial invocation there must be K² elements in input buffer but as the merging progresses there can be lesser and lesser elements. If at some instance there are not sufficient input elements to satisfy the K³ condition then it simply outputs what is there.

Complexity of Funnel Sort:

The cache complexity of funnel sort is O(N/B logM/BN/B).

Where

N = Input size

M = Size of Cache

B = Size of Block (line)

N/B = Total number of blocks transferred from higher level memory to lower level, so we have N/B blocks in cache to sort, similarly N/B can also be the maximum number of cache misses.

Drawbacks of Funnel Sort:

1. In practice it is not always possible to split K-Funnel into √K bottom funnels, it may lead to rounding errors.
   
2. The flow of data is not efficient as the both the buffers must be filled before a merge occurs (except for the last when there is no more input stream available).
   
3. vEB layout performs well for binary trees but does not perform well for complex data structures.
   

1.4.2 Lazy Funnel Sort:

In an attempt to eliminate the drawbacks of Funnel Sort, a variant of Funnel Sort called Lazy Funnel sort was introduced[4]. Lazy Funnel sort is based on binary mergers which takes two input streams as input and deliver the output as merged sorted stream.  Invocation of merger occurs through a recursive procedure which ensures that either the output buffer is full or both input streams are exhausted. 

The algorithm is given below:

Procedure Fill(v)

while out-buffer not full

if left in-buffer empty

Fill(left child)

if right in-buffer empty

Fill(right child)

perform one merge step

The procedure Fill() checks the emptiness of buffers rather than the fullness as in the case of Funnel Sort, and perform one merge step afterword.

In Lazy Funnel sort, K-merger is the basic data structure used.  A K-merger is perfect binary tree with “K-1” binary mergers and output buffer at the root of size K^{d, where d>1.}

The following figure shows a 16-merger with 15 binary mergers.

Figure 4: 16-Merger with 15 binary mergers.

For sorting N elements, lazy funnel sort recursively sort N^1/d  segments each of size N^1-1/d. N^1/d mergers are used for merging process.

The lazy Funnel Sort removes the drawbacks of Funnel Sort, for example the need to have √K bottom funnels is replaced by binary mergers, this also provide an easy and efficient implementation using vEB layout which is best in representing binary trees.

1.5Problem Statement

To explore a number of implementation issues and parameter choices for cache oblivious sorting algorithm and settle the best choices through experiments.

2Engineering the Algorithm

In this chapter, the choice for the algorithm is made, then it is discussed how the said algorithm can be optimized by tuning different parameter choices. First it is discussed which algorithm is best choice for tuning and then steps for the tuning are discussed.

2.1Methodology:

First the concentration will be on selecting an optimal algorithm for cache oblivious sorting. After the selection of algorithm, the fine tuning of the algorithm will be conducted by varying different parameter values and examining its running time. The best parameter choices will then be used to construct the most optimal sorting algorithm. After the construction of most optimal cache oblivious sorting algorithm, it will be tested against a number of present day algorithms and the running time will be observed on different hardware architectures. Figure 5 provides details of different hardware architectures used.

Figure 5: Specification of Machines.

2.2 Selecting Cache Oblivious Sorting Algorithm

There are three approaches for cache oblivious sorting algorithm, namely Funnel Sort, Lazy Funnel Sort and Distribution based Algorithm. All the three have same optimal bound O(N/B log_M/BN/B)  but the fact is that Funnel Sort and Distribution based Algorithms are structurally more complex than Lazy Funnel Sort, so Lazy Funnel Sort is the algorithm selected based on the structural simplicity.

2.3 Optimizing Lazy Funnel Sort

To optimize Lazy Funnel Sort some of its parameters and design issues can be tuned to get optimum results, some of these choices include:

• K-Merger Structure – How should the funnel be laid out in memory?
• Degree of Basic Merger—Is binary merger the optimum choice?
• Parameter α and d?
• α and d are variables that effect the output buffer size αK^d

2.3.1 K-Merger Structure:

The optimal choice to represent funnel in memory happened to be vEB layout, similarly best results were obtained when recursive invocation was used instead of iterative method.  Further the pointer based invocation produced better results than implicit navigation.

2.3.2 Degree of Basic Merger:

The experiments showed that instead of using two way basic mergers, four way merger produced better results.  The obvious reason for this is that four way mergers eliminate every other level in tree and thus reducing the overall flow of data.

2.3.3 Parameter α and d:

Experiments were performed to find the optimum choice for α and d. Different combinations were checked for d = [1.5;3] and α= [1;40]. The optimum results reflected from the experiments were α≈16, d ≈ 2.5

2.4 Implementation of Lazy Funnel Sort:

After performing the experiments to find the optimal choices for different design and parameter choices, the optimum Lazy Funnel Sort was implemented.  As the original version of Lazy Funnel Sort uses binary merger so it was decided to implement two version FunnelSort2 and FunnelSort4 for binary and 4 way basic merger respectively with the following values:

• Recursive implementation of pointer based vEB layout.
  
• (α,d) = (16, 2)

2.5 Selecting Competitors for Lazy Funnel Sort:

The competitors selected are:

1. Quick Sort implementation
   

• std::sort, for STL library of GCC v 3.2 (GCC)
  
• std::sort, for STL library of Intel C++ v 7.0 (Dink)
  
• Authors own implementation based on Bentley and McIlroy (Mix)

    2.   Cache Aware Sorting Algorithm

• TPIE sorting routine AMI_SORT
  
• R-merge
  
• msort-c
  
• msort-m
  

TPIE is library for external memory computation and are the algorithms are highly optimized.  R-merge is also a cache aware algorithm. The other cache aware algorithms selected are msort-c and msort-m [5].

3. Experiments and Results:

3.1 Experimental setup:

The experiments were performed on entire data being in RAM as well as on inputs residing on disk. The experiments were performed 21 times and median was reported. In external memory the experiments were performed only once.

3.2 Results

3.2.1 Lazy Funnel Sort Vs QuickSort

Lazy Funnel Sort performs better on small input sizes in RAM but looses to GCC QuickSort by 10-40% but on larger input sizes the gain ratio of lazy funnel sort is almost the same against the competitors on three architectures. The two architectures where Lazy Funnel Sort was outperformed  by GCC were MIPS 10000 and Pentium 4. The justification for the better performance of GCC on MIPS is that MIPS has slow processor speed and Pentium 4 is using PC800 bus which causes a delay in access time to RAM.

3.2.2 Lazy Funnel Sort Vs Cache Aware Sorting Algorithms

Lazy Funnel Sort performs better against two of the cache aware sorting algorithms msort-c and msort-m. Against R-merge Lazy Funnel Sort performs better on all architectures except MIPS. The obvious reason for this is the fact that MIPS is RISC based architecture having large number of registers, something which R-merge is designed to exploit.

Similarly for the experiments performed on disk, TPIE leads the way. FunnelSort is second and performs better than GCC. The performance gain over GCC increases as the input size grows.

Fig 6: Results for experiments performed on Pentium III

3.3 Conclusion

A careful implementation of Lazy Funnel Sort performs better in most of the experiments. It was also observed that in situation when Lazy Funnel Sort was outperformed by the competitors it was not by high margin and Lazy Funnel Sort was second best. Similarly Lazy Funnel Sort was also competitive on both RAM and disk and was the best algorithm to adapt to changes in memory hierarchy.

References:

[1] Frederik Ronn, Cache-Oblivious Searching and Sorting, Master's Thesis, Department of Computer Science, University of Copenhagen, 2003

[2] E. Demaine, Cache-Oblivious Algorithms and Data Structures, Preliminary lecture notes - handed out at the EFF Summer School on Massive Data Sets. June 27-July 1, BRICS, University of Aarhus.

[3] M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In 40th Annual Symposium on Foundations of Computer Science,pages 285–297. IEEE Computer Society Press, 1999.

[4] G. S. Brodal and R. Fagerberg, Cache-Oblivious Distribution Sweeping, Proceedings of the 29th International Colloquium on Automata, Languages, and Programming, Lecture Note in Computer Science 2380, Springer-Verlag (2002), 426-438.

[5] L. Xiao, X. Zhang, and S. A. Kubricht. Improving memory performance of sorting algorithms. ACM Journal of Experimental Algorithmics, 5(3), 2000.