Radix Selection Optimizations

In my previous blog post on Radix Selection, the algorithm which returns the k-th largest value from an unsorted array was shown to be significantly faster than sorting, because it performs less work. In this blog, I’ll explore further optimizations to make Radix Sort even faster. More Bits Per Digit Radix Sort (LSD and MSD […]

Read more "Radix Selection Optimizations"

Radix Selection Algorithm

There is a closely related algorithm to sorting called Selection, which provides the k-th element from an unsorted array. For example, a 17-th highest test score from a college Physics class, or a 91-st most popular book at the library. One way to accomplish Selection is to sort the array and then access the k-th […]

Read more "Radix Selection Algorithm"

Power Usage of Algorithms in C#

Algorithms power the world – from search to streaming to AI. Each algorithmic domain has a variety of algorithms to choose from, with different run times and characteristics. But how much power do algorithms use? Does power usage vary between algorithms? Are some algorithms more power efficient than others? This blog answers these questions by […]

Read more "Power Usage of Algorithms in C#"

Testing the Tester

Unit testing and integration testing are ubiquitous for software development and chip design. Unit testing consists of numerous test cases which test various aspects of the unit/device under test. Typically, unit test cases make sure that all required behaviors are performed by the unit under test. One problem that comes up time and time again […]

Read more "Testing the Tester"

ParlayLib Parallel Algorithms Library

Professor Blelloch and his team at Carnegie Mellon University have designed and developed a parallel algorithms library over the last decade – ParlayLib. It provides numerous parallel algorithms targeting shared-memory multicore processors. It is similar to Intel’s Threading Building Blocks (TBB), providing a works-stealing scheduler, but also goes beyond with support for additional parallel primitives […]

Read more "ParlayLib Parallel Algorithms Library"

Parallel Acceleration at Small Scale

In my previous blogs, performance acceleration via parallelism worked well for large problems, but for small problems slowed performance down significantly. A solution to this dilemma was suggested, which applied 1 core for the smallest problems, 2 cores for larger problems, and so on, scaling the number of cores to the problem size – avoiding […]

Read more "Parallel Acceleration at Small Scale"