Finding the Door in the Memory Wall, Part 2

By Erik Hagersten

March 23, 2009

Trading Parallelism for Performance

It is a common belief that only sequential applications need to be adapted for parallel execution on multicore processors. However, many existing parallel algorithms are also a poor fit. They have simply been optimized for the wrong design parameters.

In the past we have been striving for algorithms to maximize parallelism and at the same time minimize the communication between the threads. For multicore processors, however, the cost of thread communication is relatively cheap as long as the communicated data resides in a cache shared by the threads. Also, the amount of parallelism that can be explored by a multicore processor is limited by its number of cores multiplied by the number of threads running on each core. Instead, a third parameter is gaining importance for parallel multicore applications: the memory usage.

In this, the second article of the series, we contrast the behavior of a highly parallel state-of-the-art algorithm with that of a moderately-parallel algorithm in which some of the parallelism has been traded for lower DRAM bandwidth demands. We show the latter outperforms the highly parallel algorithm by a factor three on today’s multicore processors. The techniques used and some of the performance numbers are summarized here. A more detailed description of the algorithms discussed in this paper was presented at ICS 2006 together with colleagues and students from Uppsala University.

Highly Parallel Algorithm

The Gauss-Seidel algorithm (GS) is used to smooth an array with NxN elements. The original GS algorithm is pictured in Figure 1a. The new value (yellow) for each element of an NxN array is calculated as the average of its own and its four neighbors’ values. The elements of the array are updated row-wise. The element numbers in the figure refer to their iteration age. At the end of each iteration, convergence is checked and, if the condition is not met, the array will be iterated again. Typically, the array is iterated 10–30 times before the convergence is met. The red arrows in Figure 1a indicate the data dependences of this algorithm. The new values to the left of and above the yellow element have to be calculated before the yellow value can be calculated. These data dependencies make the original algorithm hard to parallelize. Memory Wall Part 2 - Fig 1

Figure 1b shows the popular red/black variation of the algorithm, where only every other element is updated in a sweep of the array (the update of red elements is shown in Figure 1b). In a second sweep, the other (black) elements are updated. Unlike the original scheme, this red/black algorithm has no data dependencies during sweeps since red elements do not depend on any other red elements. In other words, all the elements of a sweep can theoretically be updated in parallel – its parallelism is N2/2.

Figure 1c shows how two cores may divide the work. This scheme keeps the communication between the cores at a minimum: only values of the element on the boarder between the threads need to be communicated, and the threads only need to synchronize once per sweep. So, according to the old definition of a good algorithm, the red/black algorithm is close to perfect: plenty of parallelism and a minimum of communication. There is only one drawback: it runs slowly on a multicore processor, as shown in Figure 2.
Memory Wall Part 2 - Fig 2

Typically, the array size used with Gauss-Seidel is too large to fit in a multicore processor cache. Each iteration will force the entire array to be read from memory. Actually, for the red/black scheme, the array will have to be read twice per iteration, first during the red updates and then during the black updates. This will quickly saturate the DRAM bandwidth and limit the performance on a multicore processor.

Finding the Door in the Memory Wall

Instead of just maximizing parallelism, we could try to minimize DRAM bandwidth usage for a GS implementation. If we apply a blocking scheme to the original GS algorithm, we could keep an active subset of the array, called a block, in the cache and reuse these elements many times before the data are evicted from the cache. Because of the data dependence of the original GS algorithm (the red arrows in Figure 1a) we have to apply a sliding blocking technique, shown in Figure 3a. The active block inside the red frame shown includes three rows. Once the next iteration values for all the elements in the block have been updated, as shown in 3a, the block is slid down one row, as shown in Figure 3b, and the next iteration values for those elements are updated. This improves the reuse of element values while they reside in the cache. Using this scheme, each element of the array will advance three iterations per sweep, which means that the array is only read from DRAM every third iteration. This implies that only one sixth of the DRAM bandwidth is needed compared with the red/black algorithm.

If the number of rows in the active block increases, even less DRAM bandwidth will be needed. Figure 4 shows the relationship between bandwidth usage and block size, as shown by the ThreadSpotter tool for different cache sizes. A typical last-level multicore cache is in the 2-12 Mbyte range. Bandwidth demand can be reduced in this range by more than an order of magnitude using the blocking GS scheme instead of the red/black GS scheme.

Figure 3c shows a parallel version of the blocked GS. A drawback is that the threads will have to synchronize row-wise to make sure the thread to the left stays slightly ahead of the thread to the right. In sum, the blocked GS algorithm produces about an order of magnitude more thread communication than red/black GS. Also, its parallelism is much worse, in the order of N parallel threads (one per column) can help out simultaneously, compared with the N2/2 parallelism of the red/black algorithm. Still, it outperforms the red/black algorithm by a factor of three on a dual-socket quad-core system thanks to the much lower DRAM bandwidth need. Similar results have been observed when comparing 3D versions of the algorithms. Figure 5 compares the performance of the two algorithms when running on a two-socket quad-core system. The red/black saturates the bandwidth already at two active cores, while the sliding GS algorithm scales well even on a two-socket system without any special thread applied.

Summing Up

In Part 1 of this article series, we saw how a throughput workload created a superlinear slowdown on a multicore architecture due to increased cache pressure, and in this article — Part 2 of the series — we were forced to change “the ideal” highly parallel and low-communication algorithm in order for it to run well on a multicore processor. This once more drives home the point made by Sanjiv Shah a couple of weeks ago: only focusing on parallelism is not always the best way to get good performance on a multicore architecture. In Part 3, we will take a look at various techniques for identifying when optimizations are needed and compare a few simple optimization tricks.

About the Author

Erik Hagersten is chief technology officer at Acumem, a Swedish-based company that offers performance analysis tools for modern processors. He was the chief architect for high-end servers at Sun Microsystems (the former Thinking Machines development team) for six years before moving back to Sweden in 1999. Erik was a consultant to Sun until Acumem started in 2006. Since 2000 his research team at Uppsala University has developed the key technology behind Acumem.

Subscribe to HPCwire's Weekly Update!

Be the most informed person in the room! Stay ahead of the tech trends with industy updates delivered to you every week!

AWS Embraces FPGAs, ‘Elastic’ GPUs

December 2, 2016

A new instance type rolled out this week by Amazon Web Services is based on customizable field programmable gate arrays that promise to strike a balance between performance and cost as emerging workloads create requirements often unmet by general-purpose processors. Read more…

By George Leopold

AWS Launches Massive 100 Petabyte ‘Sneakernet’

December 1, 2016

Amazon Web Services now offers a way to move data into its cloud by the truckload. Read more…

By Tiffany Trader

Weekly Twitter Roundup (Dec. 1, 2016)

December 1, 2016

Here at HPCwire, we aim to keep the HPC community apprised of the most relevant and interesting news items that get tweeted throughout the week. Read more…

By Thomas Ayres

HPC Career Notes (Dec. 2016)

December 1, 2016

In this monthly feature, we’ll keep you up-to-date on the latest career developments for individuals in the high performance computing community. Read more…

By Thomas Ayres

Lighting up Aurora: Behind the Scenes at the Creation of the DOE’s Upcoming 200 Petaflops Supercomputer

December 1, 2016

In April 2015, U.S. Department of Energy Undersecretary Franklin Orr announced that Intel would be the prime contractor for Aurora: Read more…

By Jan Rowell

IBM and NSF Computing Pioneer Erich Bloch Dies at 91

November 30, 2016

Erich Bloch, a computational pioneer whose competitive zeal and commercial bent helped transform the National Science Foundation while he was its director, died last Friday at age 91. Bloch was a productive force to be reckoned. During his long stint at IBM prior to joining NSF Bloch spearheaded development of the “Stretch” supercomputer and IBM’s phenomenally successful System/360. Read more…

By John Russell

Pioneering Programmers Awarded Presidential Medal of Freedom

November 30, 2016

In an awards ceremony on November 22, President Barack Obama recognized 21 recipients with the Presidential Medal of Freedom, the Nation’s highest civilian honor. Read more…

By Tiffany Trader

Seagate-led SAGE Project Delivers Update on Exascale Goals

November 29, 2016

Roughly a year and a half after its launch, the SAGE exascale storage project led by Seagate has delivered a substantive interim report – Data Storage for Extreme Scale. Read more…

By John Russell

AWS Launches Massive 100 Petabyte ‘Sneakernet’

December 1, 2016

Amazon Web Services now offers a way to move data into its cloud by the truckload. Read more…

By Tiffany Trader

Lighting up Aurora: Behind the Scenes at the Creation of the DOE’s Upcoming 200 Petaflops Supercomputer

December 1, 2016

In April 2015, U.S. Department of Energy Undersecretary Franklin Orr announced that Intel would be the prime contractor for Aurora: Read more…

By Jan Rowell

Seagate-led SAGE Project Delivers Update on Exascale Goals

November 29, 2016

Roughly a year and a half after its launch, the SAGE exascale storage project led by Seagate has delivered a substantive interim report – Data Storage for Extreme Scale. Read more…

By John Russell

Nvidia Sees Bright Future for AI Supercomputing

November 23, 2016

Graphics chipmaker Nvidia made a strong showing at SC16 in Salt Lake City last week. Read more…

By Tiffany Trader

HPE-SGI to Tackle Exascale and Enterprise Targets

November 22, 2016

At first blush, and maybe second blush too, Hewlett Packard Enterprise’s (HPE) purchase of SGI seems like an unambiguous win-win. SGI’s advanced shared memory technology, its popular UV product line (Hanna), deep vertical market expertise, and services-led go-to-market capability all give HPE a leg up in its drive to remake itself. Bear in mind HPE came into existence just a year ago with the split of Hewlett-Packard. The computer landscape, including HPC, is shifting with still unclear consequences. One wonders who’s next on the deal block following Dell’s recent merger with EMC. Read more…

By John Russell

Intel Details AI Hardware Strategy for Post-GPU Age

November 21, 2016

Last week at SC16, Intel revealed its product roadmap for embedding its processors with key capabilities and attributes needed to take artificial intelligence (AI) to the next level. Read more…

By Alex Woodie

SC Says Farewell to Salt Lake City, See You in Denver

November 18, 2016

After an intense four-day flurry of activity (and a cold snap that brought some actual snow flurries), the SC16 show floor closed yesterday (Thursday) and the always-extensive technical program wound down today. Read more…

By Tiffany Trader

D-Wave SC16 Update: What’s Bo Ewald Saying These Days

November 18, 2016

Tucked in a back section of the SC16 exhibit hall, quantum computing pioneer D-Wave has been talking up its new 2000-qubit processor announced in September. Forget for a moment the criticism sometimes aimed at D-Wave. This small Canadian company has sold several machines including, for example, ones to Lockheed and NASA, and has worked with Google on mapping machine learning problems to quantum computing. In July Los Alamos National Laboratory took possession of a 1000-quibit D-Wave 2X system that LANL ordered a year ago around the time of SC15. Read more…

By John Russell

Why 2016 Is the Most Important Year in HPC in Over Two Decades

August 23, 2016

In 1994, two NASA employees connected 16 commodity workstations together using a standard Ethernet LAN and installed open-source message passing software that allowed their number-crunching scientific application to run on the whole “cluster” of machines as if it were a single entity. Read more…

By Vincent Natoli, Stone Ridge Technology

IBM Advances Against x86 with Power9

August 30, 2016

After offering OpenPower Summit attendees a limited preview in April, IBM is unveiling further details of its next-gen CPU, Power9, which the tech mainstay is counting on to regain market share ceded to rival Intel. Read more…

By Tiffany Trader

AWS Beats Azure to K80 General Availability

September 30, 2016

Amazon Web Services has seeded its cloud with Nvidia Tesla K80 GPUs to meet the growing demand for accelerated computing across an increasingly-diverse range of workloads. The P2 instance family is a welcome addition for compute- and data-focused users who were growing frustrated with the performance limitations of Amazon's G2 instances, which are backed by three-year-old Nvidia GRID K520 graphics cards. Read more…

By Tiffany Trader

Think Fast – Is Neuromorphic Computing Set to Leap Forward?

August 15, 2016

Steadily advancing neuromorphic computing technology has created high expectations for this fundamentally different approach to computing. Read more…

By John Russell

The Exascale Computing Project Awards $39.8M to 22 Projects

September 7, 2016

The Department of Energy’s Exascale Computing Project (ECP) hit an important milestone today with the announcement of its first round of funding, moving the nation closer to its goal of reaching capable exascale computing by 2023. Read more…

By Tiffany Trader

HPE Gobbles SGI for Larger Slice of $11B HPC Pie

August 11, 2016

Hewlett Packard Enterprise (HPE) announced today that it will acquire rival HPC server maker SGI for $7.75 per share, or about $275 million, inclusive of cash and debt. The deal ends the seven-year reprieve that kept the SGI banner flying after Rackable Systems purchased the bankrupt Silicon Graphics Inc. for $25 million in 2009 and assumed the SGI brand. Bringing SGI into its fold bolsters HPE's high-performance computing and data analytics capabilities and expands its position... Read more…

By Tiffany Trader

ARM Unveils Scalable Vector Extension for HPC at Hot Chips

August 22, 2016

ARM and Fujitsu today announced a scalable vector extension (SVE) to the ARMv8-A architecture intended to enhance ARM capabilities in HPC workloads. Fujitsu is the lead silicon partner in the effort (so far) and will use ARM with SVE technology in its post K computer, Japan’s next flagship supercomputer planned for the 2020 timeframe. This is an important incremental step for ARM, which seeks to push more aggressively into mainstream and HPC server markets. Read more…

By John Russell

IBM Debuts Power8 Chip with NVLink and Three New Systems

September 8, 2016

Not long after revealing more details about its next-gen Power9 chip due in 2017, IBM today rolled out three new Power8-based Linux servers and a new version of its Power8 chip featuring Nvidia’s NVLink interconnect. Read more…

By John Russell

Leading Solution Providers

Vectors: How the Old Became New Again in Supercomputing

September 26, 2016

Vector instructions, once a powerful performance innovation of supercomputing in the 1970s and 1980s became an obsolete technology in the 1990s. But like the mythical phoenix bird, vector instructions have arisen from the ashes. Here is the history of a technology that went from new to old then back to new. Read more…

By Lynd Stringer

US, China Vie for Supercomputing Supremacy

November 14, 2016

The 48th edition of the TOP500 list is fresh off the presses and while there is no new number one system, as previously teased by China, there are a number of notable entrants from the US and around the world and significant trends to report on. Read more…

By Tiffany Trader

Intel Launches Silicon Photonics Chip, Previews Next-Gen Phi for AI

August 18, 2016

At the Intel Developer Forum, held in San Francisco this week, Intel Senior Vice President and General Manager Diane Bryant announced the launch of Intel's Silicon Photonics product line and teased a brand-new Phi product, codenamed "Knights Mill," aimed at machine learning workloads. Read more…

By Tiffany Trader

CPU Benchmarking: Haswell Versus POWER8

June 2, 2015

With OpenPOWER activity ramping up and IBM’s prominent role in the upcoming DOE machines Summit and Sierra, it’s a good time to look at how the IBM POWER CPU stacks up against the x86 Xeon Haswell CPU from Intel. Read more…

By Tiffany Trader

Beyond von Neumann, Neuromorphic Computing Steadily Advances

March 21, 2016

Neuromorphic computing – brain inspired computing – has long been a tantalizing goal. The human brain does with around 20 watts what supercomputers do with megawatts. And power consumption isn’t the only difference. Fundamentally, brains ‘think differently’ than the von Neumann architecture-based computers. While neuromorphic computing progress has been intriguing, it has still not proven very practical. Read more…

By John Russell

Dell EMC Engineers Strategy to Democratize HPC

September 29, 2016

The freshly minted Dell EMC division of Dell Technologies is on a mission to take HPC mainstream with a strategy that hinges on engineered solutions, beginning with a focus on three industry verticals: manufacturing, research and life sciences. "Unlike traditional HPC where everybody bought parts, assembled parts and ran the workloads and did iterative engineering, we want folks to focus on time to innovation and let us worry about the infrastructure," said Jim Ganthier, senior vice president, validated solutions organization at Dell EMC Converged Platforms Solution Division. Read more…

By Tiffany Trader

Container App ‘Singularity’ Eases Scientific Computing

October 20, 2016

HPC container platform Singularity is just six months out from its 1.0 release but already is making inroads across the HPC research landscape. It's in use at Lawrence Berkeley National Laboratory (LBNL), where Singularity founder Gregory Kurtzer has worked in the High Performance Computing Services (HPCS) group for 16 years. Read more…

By Tiffany Trader

Micron, Intel Prepare to Launch 3D XPoint Memory

August 16, 2016

Micron Technology used last week’s Flash Memory Summit to roll out its new line of 3D XPoint memory technology jointly developed with Intel while demonstrating the technology in solid-state drives. Micron claimed its Quantx line delivers PCI Express (PCIe) SSD performance with read latencies at less than 10 microseconds and writes at less than 20 microseconds. Read more…

By George Leopold

  • arrow
  • Click Here for More Headlines
  • arrow
Share This