Parallel Summing Without Threads

-
Calculating the sum of an array of numbers is a simple task:

      sum = 0; 

       for each number in an array
          sum += number; 

However, summing is an important primitive function of databases and other applications, and needs to be sped up when the size of the array increases to a huge number such as 100M+. Using threads is probably the first impulse since this is such an easily parallizeable problem. But for a smaller array, such as one containing 10 numbers, multi-threading will make a summing function slower than the naive version because of the extra resources used.

So, how can a summing function be implemented so that it is always faster than the naive version?

To answer that question, let's first understand how the machine works. 
Memory Hierarchy



This diagram shows the memory hierarchy. According to the book Computer Architecture, the access time of the main memory is up to 1,000,000 times faster than the access time of the disk. The access time of the cache is up to 500 times faster than the access time of the main memory. Finally, the access time of the registers is up to 100 times faster than the access time of the cache.

When an array of numbers is resident in memory (maybe read from on disk data files), the numbers have to be loaded into the cache and registers before the CPU can add them. The key issue is how to prevent CPU from waiting. This is called "stalling."

As it turns out, there is a concept called the cache line: the CPU loads data in small batches such as 32 or 64 bytes at a time. Also, all CPUs nowadays have support for superscalar.

Given this knowledge, we can leverage this intrinsic parallelism without explicitly using threads!

      sub_sum1 = 0; ... sub_sumX= 0; 
      for every X numbers in the array:  
          sub_sum1  += number; 
          ...
          sub_sum X += number; 

This technique is also called loop unrolling.

I implemented this in both C and Java.

For C, use -O2, -O4 when compiling to optimize code generation. 
For Java, I also tried it with java -server -client when running in terminal.

The fastest was the unroll 4. Compared to unrolling 2, it was almost 1.2X as fast.
For this particular code, Java in HotSpot was a little faster than C (after warming up, of course).

Here are the numbers...





Loop unrolling helps to halve the performance for non trivial size arrays, and it's fast for small arrays as well. 

Multi-threading and loop unrolling combined can fully utilize the machine resources. 

Popular posts from this blog

Space Race: a simple Rust game built on the Bevy framework

-
Image
When I saw a post announcing the release of the Bevy framework  (an open source game engine written in Rust), I thought it'd be a fun way to learn Rust.  So I made Space Race , a 2 player game on top of the Bevy framework. How to Play The Astronaut moves around collecting jewels (using WASD keys). The Alien moves around trying to catch the Astronaut (using arrow keys).  The Astronaut wins if they collect at least 5 jewels and make it back to home base before the Alien catches them.  The Alien wins otherwise.  Things I learned about Rust  I had a lot of fun making & playing this game, and also got some hands on experience with Rust like working with structs enums vectors iterators traits dyn trait vs impl trait  dyn trait is used for trait objects, which are fat pointers made up of 1) a pointer to the value 2) a pointer to a vtable. A vtable is a table of methods, where each method points to its implementation, generated once at compile time. Each i...
Read more

Building a Toy Language Compiler in Go

-
Image
A follow-up to my previous post about building a toy language interpreter in Go. Throughout this post, I'll be referencing my repo . We'll go over a compiler which translates source code to machine code, and then a VM to execute this machine code. What is a compiler?  A compiler takes source code and translates it to executable machine code . (See my previous post for more details.) The figure below shows the high-level architecture of a simple compiler. Like the interpreter we built previously, our compiler has a lexer and a parser which turn our source code into an AST . This is our compiler's frontend . However, that's where a compiler diverges.  The compiler may translate the AST into at least one internal representation (IR) . The IR(s) may be represented using any data structure (even another AST!), but they should follow two rules: (1) be easy to produce, (2) be easy to translate into the target machine code. The IR can also be optimized...
Read more

tldr: Raft + Implementation Tips

-
Image
Part of the tldr series , which summarizes papers I'm currently reading. Inspired by the morning paper . Raft (Extended Version) + Implementation Tips [2014] Ongaro et al. Note: For implementation tips, see the end of this blog post.  Introduction Consensus algorithms The r eplicated state machine approach  is useful for providing fault-tolerance in distributed systems. It lets a cluster of unreliable machines continue operating even when some of its members fail. In this approach, machines   usually use a replicated log to stay in sync. As shown in the figure below, each server's log stores the same commands in the same order. Every state machine executes commands from its own log in order. State machines are deterministic, so each produces the same order of outputs. Once the majority of machines have responded, the command is done executing. Consensus algorithms ensure that the replicated log stays consistent. In the figure above, clients s...
Read more