TweetFollow Us on Twitter

September 94 - BALANCE OF POWER

BALANCE OF POWER

Tuning PowerPCMemory Usage

DAVE EVANS

[IMAGE 017-019_Balance_of_Pwr_h1.GIF]

If you care about the performance of code you write for the Power Macintosh, memory usage should be your foremost concern. With the PowerPCTM601 processor today, and even more important with future processors, memory usage of your code will have the greatest effect on its performance. Poorly written code will execute at a fraction of its potential, and often very simple changes will greatly improve the execution speed of your critical code.

Processors are improving much faster than the memory subsystems that support them. As the PowerPC chips move from 80 MHz to 100 MHz and beyond, their thirst for data to process and instructions to execute will increasingly tax memory. Memory caches attempt to mitigate that thirst, and all PowerPC processors come equipped with built-in caches. But your code can work well with a cache or it can work very poorly with a cache. I'll show you why and discuss what you can do to optimize your memory usage.

CACHE BASICS
As you know, a cache is simply very fast RAM that the processor can access quickly and that it uses to store recently referenced data and code. On the PowerPC processors, any data stored in the cache can be accessed without stalling the processor's pipeline. Accesses to data not in the cache will take about 20 times as long reading from main memory, or even 1 million times as long if the access causes a page fault with virtual memory. Getting and keeping your performance-critical code and data in the cache are therefore key to your execution speed.

A cache is divided into small blocks calledcache lines . On the PowerPC 601, for example, the cache has 1024 cache line blocks, each holding 32 bytes. In addition, the 601 will fetch two blocks when it can, making the cache line size effectively 64 bytes.

The first PowerPC processors have set associative caches of different sizes. The 601 has an eight-way set associative, unified cache that's 32K in size, and the 603 has a two-way set associative, split cache with 8K for data and 8K for instruction code. The termset associative refers to the way the cache relates to main memory, which is important to your performance. In some simple caching schemes, each cache line maps directly to specific areas of main memory; any access to one of these areas loads bytes into that cache line. But on the PowerPC processor, sets of cache lines are combined and then mapped to memory. There are eight cache lines in each set on the 601, and two in each set on the 603. An access to one of the areas mapped to a set will load bytes into the last-used cache line of the set, keeping the most frequently used cache lines from being purged. This more complicated scheme typically yields much better performance than the directly mapped cache.

CACHE THRASHING
The cache will most affect your performance when you're accessing large amounts of data. A typical example of this is walking through arrays to perform some operation. The best strategy is to minimize cache collisions during your accesses, and the best tactic for this is to access your data as sequentially as possible. If you walk through memory sequentially, you'll load the cache every 64 bytes, but all 64 bytes will be available for fast processing. Here's an example:

unsigned longdata[64][1024];
for (row = 2; row < 64; row++)
    for (column = 0; column < 1024; column++)
        data[row][column] =
            data[row-1][column] + data[row-2][column];

This example performs additions on each element of a large matrix and accesses that matrix sequentially in memory. It walks across each row, adding elements and storing the result. But just inverting the loops can significantly change the way memory is accessed:

unsigned longdata[64][1024];
for (column = 0; column < 1024; column++)
    for (row = 2; row < 64; row++)
        data[row][column] =
            data[row-1][column] + data[row-2][column];

Reversing the loops leads to less than optimal performance since we perform each addition for all the columns before moving to the next element of a row. Instead of sequential access, this access pattern jumps across memory in even steps of 4K. Unfortunately, on the PowerPC processor these accesses map to the same set of cache lines, and every operation causes the cache to reload from main memory. This second example takes twice as long to execute the same calculation on a Power Macintosh 6100/60.

By paying attention to how your code accesses memory, you can avoid serious cache thrashing like that done by the second example. Things to look out for are loops that iterate for a power of 2 steps (128, 256, and so on)and code whose memory accesses are not close together.

An approach called blocking may help your loops. Often your code isn't as simple as above, and your memory accesses aren't regular during the loop. If you're walking two different arrays with different increments through memory, it may be impossible to serialize your accesses. Blocking performs the calculations in blocks of rows and columns. Instead of iterating across all the columns and then proceeding to the next row, you divide the dimensional space into blocks and calculate one whole block at a time. In this next example, we calculate the multiplication of two matrices.

long result[64][64], foo[64][128], bar[128][64];
for (row = 0; row < 64; row++)
    for (column = 0; column < 64; column++) {
        long    sum = 0;
        for (i = 0; i < 128; i++)
            sum += foo[row][i] * bar[i][column];
        result[row][column] = sum;
    }

As this algorithm walks through memory, it accesses result and foo sequentially, but bar is accessed in 256-byte steps. Accessing bar by jumping through memory causes cache misses, and sequential elements of bar are flushed from the cache before they're needed.

By performing this operation in small blocks, we can better use the cache. The key is to use all the elements of foo and bar that are in a cache line before moving on. One way to do this is to expand the loop and perform four operations in a single iteration:

long result[64][64], foo[64][128], bar[128][64];
for (row = 0; row < 64; row++)
    for (column = 0; column < 64; column += 4) {
        long    sum1 = 0, sum2 = 0;
        long    sum3 = 0, sum4 = 0;
        for (i = 0; i < 128; i++) {
            sum1 += foo[row][i] * bar[i][column];
            sum2 += foo[row][i] * bar[i][column+1];
            sum3 += foo[row][i] * bar[i][column+2];
            sum4 += foo[row][i] * bar[i][column+3];
    }
    result[row][column] = sum1;
    result[row][column+1] = sum2;
    result[row][column+2] = sum3;
    result[row][column+3] = sum4;
    }

This expanded loop calculates a block of four cells in each iteration. This executes faster because elements of bar are read from the cache and don't always cause cache misses as in the earlier example. Notice that in the expanded inner loop, a cache line of the bar matrix will be loaded the first time that it's referenced; then the following three references to bar will occur without stalling. Using the bar elements while they're still in the cache gives us a significant improvement.

CODE STYLE
Good compilers can pay attention to your memory accesses and will optimize how you access memory. For example, load and store operations can be reordered by the compiler to occur when the data is most likely to be available. The first time data is accessed it tends to cause a cache line to load, and subsequent accesses to nearby data must also wait for the cache load to complete. The compiler may be able to help by inserting a few instructions between the loads. This way the cache line will be fully loaded when the subsequent accesses are needed.

For more information on loop expansion and instruction reordering, see the Balance of Power column in develop Issue 18.*

You can help your compiler by using local variables when you can. These tell the compiler exactly how the data will be used, enabling it to easily reorder the loads and stores for this data.

You should also carefully note memory dereferences, especially double dereferences. Although it may be obvious to you, the compiler often can't tell whether two pointers address the same object in memory. The compiler may be prevented from reordering instructions because it can't tell whether two operations are really dependent on each other, just because they contain dereferences. Here's an example:

paramBlock->size = myStructure->size;
paramBlock->offset = myStructure->offset;

Although it appears obvious, the compiler usually can't tell if paramBlock references the same memory as myStructure. In the resulting binary, the compiler will be conservative and not reorder these operations for best execution. Replacing the dereference of myStructure with local variables for size and offset will allow the compiler to fully optimize this example.

INSTRUCTION THRASHING
Your code binary itself can cause the cache to thrash as it loads to be executed. This is very hard to detect and optimize. The basic problem is that your subroutines may map to the same areas of the cache, and frequent calls among them will stall to reload the cache. Some code profilers for RISC workstations have attempted to detect this problem, but for the Macintosh I can't suggest much help. Just changing the link order of your code and then executing profiles may have an effect; some link orders will thrash more than others.

DATA STRUCTURES
The layout of your data structures can greatly affect your cache usage and your memory usage in general. For example, memory accesses that cross 64-bit memory boundaries take twice as long to process, as this forces two bus transactions. On the PowerPC 601 processor, any misaligned data access within a memory boundary takes the standard amount of time, which (because of typical Macintosh data structures) is a valuable feature of the chip; future PowerPC processors, however, may take longer to access misaligned data. If you can align your data structures, do so now. A good tactic is to keep 64-bit data at the top of your structure, followed by your 32-bit data, and so on to prevent accidental misalignment of elements. Pad the end of the structure to an even 64-bit increment if you will have arrays of structures or will allocate them on the stack. And if certain parts of your structure are accessed much more often than other parts, keep these together so that they stay in the cache, and make sure they're aligned.

DON'T FORGET
The memory usage of your speed-critical code will greatly affect its performance today, and current problems will just get worse when PowerPC processors go above 100 MHz. Profile your code to find the most critical bottlenecks; then pay close attention to how that code addresses memory. You'll be rewarded with an excellent return on your investment.

DAVE EVANS occasionally uses the combinatorics skills he learned at the Massachusetts Institute of Technology, but more often he's been practicing his combination punches at a Thai kickboxing gym. Designing fast algorithms for Apple's OS Platforms Group is definitely rewarding, but developing a fast left hook really gets him pumped up. *

Thanks to Tom Adams, Mike Cappella, Rob Johnston, and Mike Neil for reviewing this column. *

 

Community Search:
MacTech Search:

Software Updates via MacUpdate

GraphicConverter 10.5.1 - $39.95
GraphicConverter is an all-purpose image-editing program that can import 200 different graphic-based formats, edit the image, and export it to any of 80 available file formats. The high-end editing... Read more
Delicious Library 3.7 - Import, browse a...
Delicious Library allows you to import, browse, and share all your books, movies, music, and video games with Delicious Library. Run your very own library from your home or office using our... Read more
Adobe Animate CC 2017 18.0.0.107 - Anima...
Animate CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Flash Professional customer). Animate CC 2018 (was Flash CC) lets you... Read more
Adobe After Effects CC 2018 15.0 - Creat...
After Effects CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous After Effects customer). The new, more connected After Effects CC... Read more
Adobe Premiere Pro CC 2018 12.0.0 - Digi...
Premiere Pro CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Premiere Pro customer). Adobe Premiere Pro CC 2018 lets you edit... Read more
Alarm Clock Pro 10.3 - $19.95
Alarm Clock Pro isn't just an ordinary alarm clock. Use it to wake you up in the morning, send and compose e-mails, remind you of appointments, randomize the iTunes selection, control an internet... Read more
Adobe Lightroom 20170919-1412-ccb76bd] -...
Adobe Lightroom is available as part of Adobe Creative Cloud for as little as $9.99/month bundled with Photoshop CC as part of the photography package. Lightroom 6 is also available for purchase as a... Read more
Adobe Illustrator CC 2018 22.0.0 - Profe...
Illustrator CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous Illustrator customer). Adobe Illustrator CC 2018 is the industry... Read more
Hopper Disassembler 4.3.0- - Binary disa...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32- and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about its... Read more
Adobe InDesign CC 2018 13.0.0.125 - Prof...
InDesign CC 2018 is available as part of Adobe Creative Cloud for as little as $19.99/month (or $9.99/month if you're a previous InDesign customer). Adobe InDesign CC 2018 is part of Creative Cloud.... Read more

ICEY (Games)
ICEY 1.0 Device: iOS Universal Category: Games Price: $2.99, Version: 1.0 (iTunes) Description: ICEY is a 2D side-scrolling action game. As you follow the narrator's omnipresent voice, you will see through ICEY's eyes and learn the... | Read more »
The best new games we played this week -...
We've made it, folks. Another weekend is upon us. It's time to sit back and relax with the best new releases of the week. Puzzles, strategy RPGs, and arcade games abound this week. There's a lot of quality stuff to unpack this week, so let's hop... | Read more »
Wheels of Aurelia (Games)
Wheels of Aurelia 1.0.1 Device: iOS Universal Category: Games Price: $3.99, Version: 1.0.1 (iTunes) Description: | Read more »
Halcyon 6: Starbase Commander guide - ti...
Halcyon 6 is a well-loved indie RPG with stellar tactical combat and some pretty good writing, too. It's now landed on the App Store, so mobile fans, if you're itching for a good intergalactic adventure, here's your game. Being a strategy RPG, the... | Read more »
Game of Thrones: Conquest guide - how to...
Fans of base building games might be excited to know that yet another entry in the genre has materialized - Game of Thrones: Conquest. Yes, you can now join the many kingdoms of the famed book series, or create your own, as you try to conquer... | Read more »
Halcyon 6: Starbase Commander (Games)
Halcyon 6: Starbase Commander 1.4.2.0 Device: iOS Universal Category: Games Price: $6.99, Version: 1.4.2.0 (iTunes) Description: An epic space strategy RPG with base building, deep tactical combat, crew management, alien diplomacy,... | Read more »
Legacy of Discord celebrates its 1 year...
It’s been a thrilling first year for fans of Legacy of Discord, the stunning PvP dungeon-crawling ARPG from YOOZOO Games, and now it’s time to celebrate the game’s first anniversary. The developers are amping up the festivities with some exciting... | Read more »
3 reasons to play Thunder Armada - the n...
The bygone days of the Battleship board game might have past, but naval combat simulators still find an audience on mobile. Thunder Armada is Chinese developer Chyogames latest entry into the genre, drawing inspiration from the explosive exchanges... | Read more »
Experience a full 3D fantasy MMORPG, as...
Those hoping to sink their teeth into a meaty hack and slash RPG that encourages you to fight with others might want to check out EZFun’s new Eternity Guardians. Available to download for iOS and Android, Eternity Guardians is an MMORPG that lets... | Read more »
Warhammer Quest 2 (Games)
Warhammer Quest 2 1.0 Device: iOS Universal Category: Games Price: $4.99, Version: 1.0 (iTunes) Description: Dungeon adventures in the Warhammer World are back! | Read more »

Price Scanner via MacPrices.net

12″ iPad Pros on sale for $50 off MSRP, no ta...
Adorama has 12″ iPad Pros on sale today for $50 off MSRP. Shipping is free, and Adorama charges sales tax in NY & NJ only: – 12″ 64GB iPad Pro: $749, save $50 – 12″ 256GB iPad Pro: $899, save $50... Read more
9″ iPads on sale for $30 off, starting at $29...
MacMall has 9″ iPads on sale for $30 off including free shipping: – 9″ 32GB iPad: $299 – 9″ 128GB iPad: $399 Read more
Apple restocks full line of refurbished 13″ M...
Apple has restocked a full line of Apple Certified Refurbished 2017 13″ MacBook Pros for $200-$300 off MSRP. A standard Apple one-year warranty is included with each MacBook, and shipping is free.... Read more
13″ 3.1GHz/256GB MacBook Pro on sale for $167...
Amazon has the 2017 13″ 3.1GHz/256GB Space Gray MacBook Pro on sale today for $121 off MSRP including free shipping: – 13″ 3.1GHz/256GB Space Gray MacBook Pro (MPXV2LL/A): $1678 $121 off MSRP Keep an... Read more
13″ MacBook Pros on sale for up to $120 off M...
B&H Photo has 2017 13″ MacBook Pros in stock today and on sale for up to $120 off MSRP, each including free shipping plus NY & NJ sales tax only: – 13-inch 2.3GHz/128GB Space Gray MacBook... Read more
15″ MacBook Pros on sale for up to $200 off M...
B&H Photo has 15″ MacBook Pros on sale for up to $200 off MSRP. Shipping is free, and B&H charges sales tax in NY & NJ only: – 15″ 2.8GHz MacBook Pro Space Gray (MPTR2LL/A): $2249, $150... Read more
Roundup of Apple Certified Refurbished iMacs,...
Apple has a full line of Certified Refurbished 2017 21″ and 27″ iMacs available starting at $1019 and ranging up to $350 off original MSRP. Apple’s one-year warranty is standard, and shipping is free... Read more
Sale! 27″ 3.8GHz 5K iMac for $2098, save $201...
Amazon has the 27″ 3.8GHz 5K iMac (MNED2LL/A) on sale today for $2098 including free shipping. Their price is $201 off MSRP, and it’s the lowest price available for this model (Apple’s $1949... Read more
Sale! 10″ Apple WiFi iPad Pros for up to $100...
B&H Photo has 10.5″ WiFi iPad Pros in stock today and on sale for $50-$100 off MSRP. Each iPad includes free shipping, and B&H charges sales tax in NY & NJ only: – 10.5″ 64GB iPad Pro: $... Read more
Apple iMacs on sale for up to $130 off MSRP w...
B&H Photo has 21-inch and 27-inch iMacs in stock and on sale for up to $130 off MSRP including free shipping. B&H charges sales tax in NY & NJ only: – 27″ 3.8GHz iMac (MNED2LL/A): $2179 $... Read more

Jobs Board

Engineering Manager, *Apple* Retail Enginee...
# Engineering Manager, Apple Retail Engineering Job Number: 58139948 Santa Clara Valley, California, United States Posted: 20-Oct-2017 Weekly Hours: 40.00 **Job Read more
*Apple* Retail - Multiple Positions - Apple,...
Job Description: Sales Specialist - Retail Customer Service and Sales Transform Apple Store visitors into loyal Apple customers. When customers enter the store, Read more
Commerce Engineer, *Apple* Media Products -...
Commerce Engineer, Apple Media Products (New York City) Job Number: 113028813New York City, New York, United StatesPosted: Sep. 20, 2017Weekly Hours: 40.00 Job Read more
US- *Apple* Store Leader Program - Apple (Un...
US- Apple Store Leader Program Job Number: VariousUnited StatesPosted: Oct. 19, 2017Retail Store Job Summary Learn and grow as you explore the art of leadership at Read more
Product Manager - *Apple* Pay on the *Appl...
Job Summary Apple is looking for a talented product manager to drive the expansion of Apple Pay on the Apple Online Store. This position includes a unique Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.