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"Under Construction… Nvidia has added standard C++ parallel algorithms on GPUs. Algorithm seq unseq par par_unseq GPUSpeedup max_element(std:: 1600 1613 1620 1581 1.0 adjacent_difference(std:: 2052 2062 996 0.5 adjacent_find(std:: 2963 2947 37 all_of(std:: 3652 3752 34 any_of(std:: 3652 3584 37 count(std:: 2999 2987 1627 equal(std:: 3839 3716 37 copy(std:: 4421 4525 1529 merge(std:: 201 197 […]
Read more "C++ Parallel STL on GPUs"My previous blog, C++ Parallel STL Benchmark, showed performance for all measured C++ Parallel Standard algorithms increased over sequential single-core implementations. Some algorithms scaled much better than others – by nearly 10X on a 14-core processor and over 20X on a 48-core. Only large arrays with 100 million integers were used for these benchmarks. Let’s […]
Read more "Can C++ Parallel Standard Algorithms Accelerate, Even Small Arrays?"C++ includes a standard set of generic algorithms, called STL (Standard Template Library). On Windows, Microsoft provides parallel versions of these algorithms, listed below with the first argument being std::. Also, Intel provides parallel implementations, listed below with the first argument being dpl::. These parallel versions utilize multiple cores of the processor, providing substantially faster […]
Read more "C++ Parallel STL Benchmark"This page provides additional resources, such as correction, additions, errata, and updates to the book. Contact Information vduvanenko2@gmail.com has been setup for correspondence about the book. Don’t hesitate to a-mail a note with questions, suggestions, corrections, improvements, or missing information. Updates Benchmarks on 12-th generation laptop (14-cores) and 4-th generation Xeon AWS node (48-core C7i.24xlarge) […]
Read more "Practical Parallel Algorithms Book Additional Resources"This blog explores methods to reach maximum read bandwidth. This is a useful basic operation which limits performance of many algorithms serial or parallel. Knowing how to reach the maximum available read bandwidth is beneficial in many instances. One way to test performance of memory reading is to implement a Summation. Summing elements of an […]
Read more "Maximum Read Bandwidth"Before synthesis, chip designers used to implement all aspects of chip design by hand. This included combinational logic implementation, storage elements such as SRAMs, flip-flops and latches. Netlist as well as place-and-route were also done fairly manually. High-level design implementations, either in C, Verilog or another high-level language, were manually translated into gates. When synthesis […]
Read more "When to Trust Chip Synthesis"This blog progressively develops a simple parallel algorithm described in Chapter 6 of a soon to be released book, as a fun parallelism exercise. The goal of this exercise is to sort a large array of unsigned bytes as quickly as possible, using multiple cores if that provides performance improvement, in-place if possible, targeting the […]
Read more "Parallel Sort of Byte Arrays"This a reprint of my September 1997 letter to IEEE Computer magazine’s Open Channel. It’s still relevant today. For instance, when designing add-in computer cards or chips that connect over PCI-express connection. Preface Back in the 1990’s when designing add-in cards for PC’s and Apple computers various busses such as PCI (precursor to PCI Express), […]
Read more "Two Writes Make a Read"This blog is a repost of an article I wrote in Dr. Dobb’s Journal in November of 2009, since Dr. Dobb’s Journal has ceased operation and its website has broken since then. The algorithm developed is a novel In-Place Radix Sort, which sorts in Linear Time. The article is still available through the amazing web […]
Read more "In-Place N-bit Radix Sort"
Algorithm Performance 