Compilers and More: Gloptimizations

By Michael Wolfe

November 9, 2007

In my last column, I discussed the performance improvements on one of the SPEC CPU2000 floating point benchmarks, 172.mgrid, between 1999 and 2006, and introduced an optimization (which we call Loop-Carried Redundancy Elimination) that improves mgrid significantly. The SPEC CPU committee has been quite careful with benchmarks that are sensitive to compiler tricks. The original SPEC ’89 benchmark suite included 030.matrix300 (dense matrix multiplication). Since matrix multiplication is one of a set of core operations performed in many numerical applications, it was considered a good candidate for a benchmark. But, to quote Reinhold Weicker from the SPEC Newsletter (December 1995): “However, if a program becomes a benchmark, compiler authors can become very creative.”

In this case, compilers were modified to aggressively tile the loops; in each tile, the program performs a sub-matrix multiplication where the submatrices fit into the cache memory, improving the total performance by up to a factor of eight. (The term “loop tiling” or “iteration space tiling” was actually suggested by my wife in 1986; I was looking for a better term to use in a paper, she was looking at the kitchen floor.) Since this one optimization had such a big impact, and didn’t apply to the other benchmarks, the SPEC committee decided that it was not a fair contributor to an overall performance metric, and matrix300 was retired in 1992.

I noted last time that Dell had published a SPEC CPU2000 run in November 1999 on a 733 MHz Pentium III Precision Workstation 420, and another in October 2006 on a 2.66 GHz Core 2 Extreme Precision Workstation 390. I chose to compare these two runs simply because they were from the same vendor seven years apart. The base CFP2000 proved from 242 to 2679, a factor of just over 11. The big winner was 179.art, which improved from a ratio of 313 to 9306, almost a factor of 30 speedup. What accounts for this factor of 30? Can we expect similar improvements for any other program?

One way to achieve great speedups is to make the base case really slow; then, even simple optimizations can deliver a nice improvement. Sometimes, the program is written in a way that seems intentionally aimed at making it run slowly. Such a case appears in ART.

The ART benchmark (Adaptive Resonance Theory neural network for image ecognition) is written in C, and the critical loop is:

    struct{
double *I; double W, X, V, U, P, Q, R;
} * f1_layer;
double **bus;
....
for( tj = 0; tj < numf2s; tj++ ){
Y[tj].y = 0;
if( !Y[tj].reset )
for( ti = 0; ti < numf1s; ti++ )
Y[tj].y += f1_layer[ti].P * bus[ti][tj];
}

This loop appears in several places in the program, and much of the time of the program is spent in it; speed up this loop and the program runs fast.

However, there are several problems here. The struct f1_layer has 8 members, each 8 bytes long (assuming 64-bit pointers). That means each element of f1_layer takes up a whole 64-byte cache line. So while we’re traversing the array f1_layer in the inner loop, we only use one value out of each cache line. Even worse, the two-dimensional array bus is dynamically allocated, and we are traversing down the columns; that means two memory accesses (to get the row pointer bus[ti], then the value bus[ti][tj]). In both cases, the program abuses memory bandwidth in the inner loop, unless the whole dataset fits in the cache.

A few more comments: it turns out the inner loop has a trip count of about 10,000, while the outer loop has only 6 iterations, and the conditional around the inner loop never trips (reset is always 0), at least not in the benchmark datasets, so the inner loop is always executed. These facts are known only at runtime, however.

I’ve seen three ways to make this loop run much faster.  Some compilers implement what has been called the ART hack, reorganizing the data for the struct f1_layer. The array-of-struct is reorganized to become a struct of arrays. It takes the same amount of space, but now each element f1_layer[ti].P become f1_layer.P[ti], so consecutive elements are adjacent in the cache, and the performance of the cache and the whole program improves greatly.

    struct{
double **I; double *W, *X, *V, *U, *P, *Q, *R;
} f1_layer;
double **bus;
....
for( tj = 0; tj < numf2s; tj++ ){
Y[tj].y = 0;
if( !Y[tj].reset )
for( ti = 0; ti < numf1s; ti++ )
Y[tj].y += f1_layer.P[ti] * bus[ti][tj];
}

I did this by hand on an older Intel 3.4GHz EM64T Xeon, using the PGI compilers, and measured a 49% performance improvement. You can imagine what kind of whole program analysis would allow or disallow this reorganization, and it is very rarely feasible. However, this benchmark is so important that some compilers take this step. Here’s an optimization (to abuse the term) that would never have been invented if not for this particular benchmark.

A different trick is to interchange the two loops. The problem being solved is the accesses to the array bus, which are non-adjacent, have no locality, and require two loads per iteration, problems which go away if the two loops are interchanged. However, after interchanging, the new inner loop has a very short trip count (though the compiler probably doesn’t know that). The other more serious problem is that interchanging the loops brings the conditional inside both loops.

    struct{
double *I; double W, X, V, U, P, Q, R;
} * f1_layer;
double **bus;
....
for( tj = 0; tj < numf2s; tj++ )
Y[tj].y = 0;
for( ti = 0; ti < numf1s; ti++ ){
for( tj = 0; tj < numf2s; tj++ )
if( !Y[tj].reset )
Y[tj].y += f1_layer[ti].P * bus[ti][tj];
}

On the same Xeon, I measured a speedup of 2.33. However, this is quite dangerous, from a performance standpoint; instead of ‘numf2s’ conditional tests, there are now ‘numf1s*numf2s’ tests. If the test tripped at all, the modified version could execute quite a bit slower than the original. Yet, at least one compiler implements this and gets more than a factor of two improvement in the whole program, mostly due to this loop transformation.

The third trick, not implemented by any compiler (yet, that I know of), is to leave the loops the way they are and to transpose the array bus (and a similarly accessed array, tds). It turns out these arrays are dynamically allocated, but accessed in the wrong dimension. If we transpose the dimensions, the performance of this loop and the whole program really screams. On that same Xeon, I measured a speedup of 4.3.

This last is somewhat harder to implement automatically. The most severe problem is that C doesn’t really have two-dimensional arrays; to get a two-dimensional dynamic array, the program has to first allocate a one-dimensional vector of pointers. To transpose an array, the program has to allocate a vector of a different size. Purists argue that the modified program might allocate more space, and hence might run out of memory for some large datasets.

Moreover, the performance improvements are not very stable. The speedups I measured on the EM64T were 1.49 for array-of-struct reorganization, 2.3 for loop interchange, and 4.3 for for array transposition. Last month, I compared performance using an older 733MHz Intel Pentium III and a 2.66GHz Intel Core 2 Extreme. The speedups for these three optimizations on these two machines (and the EM64T) are summarized here:

       EM64T   PIII      Core2
        1.49       1.64      1.08    array-of-struct reorganization
        2.33       1.00      1.03    loop interchange
        4.34       1.19      1.48    array transpose

I am guessing that these optimizations have much less effect on the latest Core 2 because the data all fits in the much larger cache.

So, last month I discussed compiler tuning for 172.mgrid, where a new optimization improved its performance about 20%; happily, we’ve found this new feature applies in many other user applications as well. This month, I presented compiler tuning for 179.art, where aggressive optimization can improve the performance by factors (on some machines). I won’t go into the hacks, tricks, and other tuning for the other SPEC CPU2000 benchmarks; the number of compiler tricks is linearly related to the number of benchmarks.

With the increased importance of benchmark performance, compiler development teams are encouraged to aggressive (or even heroic) efforts to optimize performance on these programs. The only reason they do so is that vendors and users (and compiler product managers) place artificial importance on certain benchmark results. Yet, these optimizations, while impressive, may be of little value, or no value, or even negative value among the more general user domain, or even on the same program with different inputs. As shown here for ART, the value of the optimization may decrease to essentially zero as the architecture progresses.

Therefore, in the spirit of the Golden Raspberry award (http://www.razzies.com/) and the Ig Nobel Prizes (http://www.improbable.com/ig), I propose that we honor the most outrageous, benchmark-specific optimization with an award of its own, the Gloptimization award, or Gloppy for short. The award itself would be a pile of glop (or representation thereof), defined in my American Heritage Dictionary as “n. 1. A messy mixture, as of food. 2. Something, as writing, that is worthless. v. 1. To cover with glop. 2. To put glop on.” The award, at least, is appropriate. More credit should be given to an optimization that applies to a single benchmark; extra credit if it measureably slows down other benchmarks or applications. Posthumous awards can be proposed for optimizations that are actually removed from compilers as the targeted benchmarks are themselves retired. The optimizations mentioned above would certainly be candidates for a Gloppy, though perhaps not winners.

The lesson for customers is that standard benchmarks are valuable tools, but should not be the only or primary means of comparing system performance. The best measure is always the performance of your own applications, to which the systems and accompanying software are not specifically tuned.

SPEC (R) is a registered trademark of the Standard Performance Evaluation Corporation (http://www.spec.org/).

—–

Michael Wolfe has developed compilers for over 30 years in both academia and industry, and is now a senior compiler engineer at The Portland Group, Inc. (www.pgroup.com), a wholly-owned subsidiary of STMicroelectronics, Inc. The opinions stated here are those of the author, and do not represent opinions of The Portland Group, Inc. or STMicroelectronics, Inc.

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!

Enlisting Deep Learning in the War on Cancer

December 7, 2016

Sometime in Q2 2017 the first ‘results’ of the Joint Design of Advanced Computing Solutions for Cancer (JDACS4C) will become publicly available according to Rick Stevens. He leads one of three JDACS4C pilot projects pressing deep learning (DL) into service in the War on Cancer. The pilots, supported in part by DOE exascale funding, not only seek to do good by advancing cancer research and therapy but also to advance deep learning capabilities and infrastructure with an eye towards eventual use on exascale machines. Read more…

By John Russell

DDN Enables 50TB/Day Trans-Pacific Data Transfer for Yahoo Japan

December 6, 2016

Transferring data from one data center to another in search of lower regional energy costs isn’t a new concept, but Yahoo Japan is putting the idea into transcontinental effect with a system that transfers 50TB of data a day from Japan to the U.S., where electricity costs a quarter of the rates in Japan. Read more…

By Doug Black

Infographic Highlights Career of Admiral Grace Murray Hopper

December 5, 2016

Dr. Grace Murray Hopper (December 9, 1906 – January 1, 1992) was an early pioneer of computer science and one of the most famous women achievers in a field dominated by men. Read more…

By Staff

Ganthier, Turkel on the Dell EMC Road Ahead

December 5, 2016

Who is Dell EMC and why should you care? Glad you asked is Jim Ganthier’s quick response. Ganthier is SVP for validated solutions and high performance computing for the new (even bigger) technology giant Dell EMC following Dell’s acquisition of EMC in September. In this case, says Ganthier, the blending of the two companies is a 1+1 = 5 proposition. Not bad math if you can pull it off. Read more…

By John Russell

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

Enlisting Deep Learning in the War on Cancer

December 7, 2016

Sometime in Q2 2017 the first ‘results’ of the Joint Design of Advanced Computing Solutions for Cancer (JDACS4C) will become publicly available according to Rick Stevens. He leads one of three JDACS4C pilot projects pressing deep learning (DL) into service in the War on Cancer. The pilots, supported in part by DOE exascale funding, not only seek to do good by advancing cancer research and therapy but also to advance deep learning capabilities and infrastructure with an eye towards eventual use on exascale machines. Read more…

By John Russell

Ganthier, Turkel on the Dell EMC Road Ahead

December 5, 2016

Who is Dell EMC and why should you care? Glad you asked is Jim Ganthier’s quick response. Ganthier is SVP for validated solutions and high performance computing for the new (even bigger) technology giant Dell EMC following Dell’s acquisition of EMC in September. In this case, says Ganthier, the blending of the two companies is a 1+1 = 5 proposition. Not bad math if you can pull it off. 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

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