E2 Writeups

strength reduction by Colin | Thu, 13 Oct 2005 22:28:24 | 0 comments

Strength reduction

Strength reduction is the process of simplifying a program by replacing an operation in a loop (or recursive function) with a simpler operation using state from the previous loop iteration (or function call).

The canonical example is array indexing. Consider this snippet of C code:

struct Person {
  char *name;
  unsigned age;
  unsigned height;
};

unsigned total_age_of_everyone (int n_people, struct Person people[])
{
  unsigned total = 0;
  unsigned i;
  for (i=0; i<n_people; i++)
  {
    total += people[i].age;
  }
  return total;
}

Naively, the array address in the loop must be calculated by a multiplication: the address required to access people[i] is:

	people + i * sizeof(struct Person) + sizeof(char*)

However, on most machines, that multiplication would take a while to alculate.At least a couple ofcycle s, which is annoying since the rest of the loop probably doesn't take much more than that to execute.

If our compiler is clever enough, and most of them are, it'll spot that there's a faster way to calculate that address. Between each successive iteration of the loop, that address increases by a nice, constant value: sizeof(struct Person). So instead of performing a slow multiplication, the compiler can just add sizeof(struct Person) to the value that it calculated on the last iteration.

The code the compiler produces would be equivalent to the code it would produce for:

  unsigned total = 0;
  unsigned i;
  struct Person *person_pointer = & people[0];

  for (i=0; i<n_people; i++)
  {
    total += *person_pointer++;
  }
  return total;

Note that we've introduced a loop-carried state element (person_pointer) that wasn't there before, and that where the loop previously had an expensive multiplication, it now only has an addition (which, on most architectures, can probably be merged with the load operation, saving even more on complexity).

This strength reduction can be applied to any function which can be expressed as a simpler, iterative function. For example, to compute a power series, we must calculate xⁿ (which can be quite expensive to calculate) for all values of n from 0 onwards, but each can be calculated simply from the last value by simplying multiplying by x.

I Am Asian by Colin | Fri, 29 Jul 2005 21:53:05 | 0 comments

I've had issues with McDonald's for quite a while. Almost every sane person has. We've been through McLibel and Super Size Me, we've heard about the appalling working conditions and practices of the corporation, we've heard about the condition and treatment of the animals used for meat, and we've heard about the destruction of Brazilian rainforest purely to create more grazing land for McDonald's livestock.

I'd heard all that too, but the straw that broke this camel's back, the one that made myself and herself swear never to eat in a McDonald's again (rather than simply making it a casually-adhered-to rule), was I Am Asian™.

Here's how it happened. Some while ago, someone in the (presumably gargantuan) McDonald's marketing department decided to cross-correlate the "How often do you eat in McDonalds?" and "What is your ethnicity?" results from their latest customer feedback questionnaire, and spotted that "Asian-American" customers were, on average, their least frequent visitors.

Gosh. What's a poor, multinational corporation to do in such a situation? It's a quandary, to be sure.

The answer, of course, is to whip up some highly targeted marketing. And the resulting web page can be witnessed at http://i-am-asian.com. If I may be so bold as to quote:

"We're Asian and Pacific Islander Americans and our diverse cultures and our everyday American lifestyle are becoming one. We're hanging on to our great traditions while we move to the beat of the times. We honor our heritage and we love being Americans. From high fashion to high tech, from Asian Pacific American hip hop to haute cuisine, we're weaving the threads of our culture into the fabric of everyday American life. Whether we're celebrating one of our cultural holidays or enjoying a Big Mac sandwich, we're helping make the magic mix called America become even richer. And McDonald's is right there with us, everyday! We are proud of our cultural heritage."

The copy writer for i-am-asian.com

The above copy is displayed beneath a Flash slideshow featuring various people who appear to be of 'Asian' extraction, 'Asian' in this sense meaning precisely what it does when you tick that box on the questionnaire: having ancestors from one of the myriad and diverse cultures or races that occupy the huge land mass of the continents of eastern Eurasia, Asia and the Pacific Islands. Rather a broad catchment area, isn't it?

There's a vaguely East Asian couple on a beach wearing shades, next to a paper McDonald's cup. There's a rather rotund looking chap who looks a bit like a south-east Asian Frank Black, sitting with an electric guitar (not plugged in to anything) and a McDonalds takeaway. There are some sandalled feet sticking out of a Volkswagen New Beetle cabriolet. There's a girl with roller blades and a pug dog. (Are they saying about pug noses? It's a commonly used insult, I'm told.) Then a big close up of the dog wearing a doggy-sized McDonald's "i am asian" t-shirt.

So, who wrote this copy? Who are the "we" referred to in the copy? And why does it sound like a manifesto for selling out half the world's cultural heritage for a hamburger?

I really have a hard time working out whether or not this is racist. Is it racist to isolate a demographic on this basis for the purposes of marketing? Is it racist to blatantly pander to and reinforce so many cultural stereotypes at the same time? I can't work it out, but I'm reminded of a quote from a very great man, which seems horribly appropriate right now.

"I'm not a racist!"

Father Ted Crilley

Also, if you can hear a faint screaming sound, that's probably Bill Hicks screaming from his grave, inviting the marketing department of McDonald's corporation to come join him.

Racist and insulting or not, it leaves such a bad taste in my mouth, fills me with such revulsion that it makes me want to... well, stab things. If you find the same, please feel free to spread the word as far and wide as possible. The more people know about this, the less they'll want to visit McDonalds.

Thankfully, there's a little light relief in the form of a spoof site, http://i-am-white.com, redressing the racial imbalance a little.

Spiralacing by Colin | Fri, 29 Jul 2005 21:51:58 | 0 comments

I have had, for some time, a minor obsession with shoelaces. As obsessions go, it's probably fairly innocuous, and it certainly makes for a cheap hobby. I've also been known to buy people laces as gifts. It's a thing. You gotta have a thing. A gimmick.

It stemmed partially from finally finding an Army and Navy store in Cambridge which sold proper DM bootlaces in all the colours of the rainbow, and partially from being plain old fed-up with the standard, boring criss-cross way of lacing up my boots. I'd criss-crossed them since I was old enough to lace up my own shoes. Over the years, I've experimented with something like 10 different methods of lacing up my boots, but almost always come back to the standard ladder lacing or "straight lace", done in what's apparently known as the European style (straight across on the outside, up two holes on the inside...).

Nonetheless, for the time being at least, I have a new favourite: Double helix lacing, or, as the "inventor" of the lacing method has dubbed it, "Spiralacing". That should probably have a ™ symbol next to it or something, now I come to think of it...

But let's start at the beginning. "What's wrong," I hear you cry "with the standard way of lacing up shoes?" Well, there's a bunch of things. Have a look at your shoes (or at my pathetic ASCII art rendering of a shoe, below). If they're laced up in the standard manner, with the lace passing across and from the outside of the shoe to the inside on each eyelet on the way up, there's probably a couple of things you probably haven't even thought to notice.

   _____________________________
  /     | o   o   o   o----     \
 /      \__\___\___\____/\       |
|        ___X___X___X___  |      |
|       /  /   /   /    \/______/|
|       | o   o   o   o--,       |
 \                        \      |
  '========================|====='

The laces crossing over each other generate quite a bit of friction, which can make it harder to loosen the laces for donning or doffing boots. The fact that the laces have to cross over from inside to outside means that it's impossible to completely pull the boot tight shut such that the two sides are in contact with each other. The crossing of the laces from inside to out pushes the edges of the shoe alternately up and down and can, after prolonged use, permanently crinkle the shoe, depending on what material it's made from. In addition to these, and worst of all, your shoelaces look exactly the same as those of just about every other person on the planet.

Straight lacing solves some of these problems. With the laces running straight across the outside, there's no crossing from inside to out in the middle, so the shoes may be completely shut, and the material won't be damaged by the tension. It also looks damn cool. There's a downside, though. Depending on the method used, most ladder lacing methods have laces crossing each other inside the shoe, between the flaps and the tongue. This is annoyingly inconvenient because the tongue and outer flaps push the laces together, increasing friction and making it even more difficult to loosen the laces.

Yes, but what of this "Spiralacing"?

Well, I was just getting to that. "Invented" by one Monte Fisher, "Spiralacing" is a lacing method which reduces friction and speeds the donning and doffing of boots by eliminating the need for laces to cross over each other at all, and getting rid of most (but not all) of the need for the laces to cross from the outside to the inside.

The structure of the lacing method resembles a DNA double-helix, with both sides of the lace spiralling round each other as they go up the shoe. The friction of lace-on-lace is virtually eliminated, making it incredibly easy to loosen laces as well as tighten them. Tightening the laces can even be accomplished with one hand, since all the laces on the outside are tightened by pulling in the same direction.

It doesn't quite eliminate the crossing over of laces from the outside to the inside, since it still requires one transition at the bottom to establish the twisting helix at the bottom, and one at the top to bring the laces both out to the front at the same point to be tied. Let's re-lace our ASCII shoe:

   _____________________________
  /     | o   o   o   o----     \
 /      \__\___\___\____/\       |
|        _|_X___X___X___  |      |
|       / |  \   \      \/______/|
|       | o   o   o   o--,       |
 \                        \      |
  '========================|====='

To tighten up the lace, just grab any two adjacent laces (starting at the bottom) on the outside, and pull them upwards. It's rather easy and, despite the wrinkles at the top and the bottom, and the general asymmetry, it looks quite snazzy.

You can do it clockwise or counter-clockwise, or even better use a different winding direction on each foot. Unless you're superstitious, of course.

Now explain the sarcastic quotation marks

Ah yes. Though it's not something which I'd have thought would require too much thought or experimentation to come upwith , the "inventor" of the lacing method (or at least, the first one to document it and come up with the rather catchy "Spiralacing" name) applied for, and was granted, a US patent, number 6,513,211. Possibly the worst abuse of patent law since someone patented a Method of Swinging on a Swing (US Patent number 6,368,227).

I believe he probably had some sort of plan to try and convince the US armed forces to use his lacing scheme, and charge them royalties for doing so. Fair enough, I suppose, but it does seem rather an excessive use of legal brute force.

Acknowledgements and References

A wealth of shoe-lacing information can be found at Ian Fieggen's excellent site dedicated to the purpose, located at:
http://www.fieggen.com/shoelace/lacingmethods.htm

Monte Fisher's page documenting the double helix lace is worth a read for the details of that particular lace:
http://www.lukefisher.com/lacing/

I blame this whole writeup squarely on ReiToei, for pointing me at Ian's site and thus getting this whole nerdy ball rolling.

Rosetta by Colin | Fri, 29 Jul 2005 21:48:58 | 0 comments

On the 6th of June 2005, in his keynote speech on the opening day of this year's WWDC in San Francisco, Steve Jobs announced the news that many pundits had speculated on since the days before the introduction of the G5: Apple are to begin moving their Power Mac product line from PowerPC-based CPUs to Intel x86 chips.

A controversial move, the decision was made on the basis of price and performance of the respective roadmaps for Intel processors and IBM's plans for POWER in the near future. Jumping ship may make sense in the near future, but seems something of a missed opportunity: offering support for both Intel and POWER platforms would offer flexibility and the ability to jump back should the current roadmap lead us astray. But for the immediate future, Intel seems to be the way to go.

Switching processor architectures is something that Apple have done before, from the old Motorola 680x0 architecture to the PowerPC variant of the POWER architecture. Newly compiled PowerPC applications ran with all the speed the processor could muster, whereas existing 680x0 applications were run under a 680x0 emulation layer, which impacted performance, making these applications slower on the new machines than they were on the old machines. It wasn't hot on the performance front, but at least it worked.

Apple are hoping to pull off the same trick again, this time by translating the PowerPC instruction set to native x86 code and running this on the host Intel processor of the new Macintosh computers, and 'Rosetta' is the software that will attempt this.

In the twelve years that have passed since Apple introduced the original Power Mac, emulation technology has moved on a great deal. Digital Equipment Corporation pioneered work on code translation with their FX!32 product, which allowed a DEC Alpha workstation running Windows NT to execute applications compiled for Intel. This work spawned Transmeta's code morphing technology, utilising sophisticated dynamic code translation and dynamic optimisation to simulate the x86 instruction set on a custom low-power processor. Virtual PC for Macintosh and PearPC for Windows and Linux on x86 both use code translation of varying sophistication to execute x86 or PowerPC (respectively!) on their opposing host architectures.

Scope

If you've seen PearPC (or, heaven forfend, CherryOS) in action, you might be skeptical. Fortunately for early adopters of the new Intel-based Macs, running PowerPC Mac OS X programs on x86 isn't nearly as hard as PearPC makes it seem. PearPC has the unenviable task of simulating the behaviour of an entire CHRP PowerPC-based microcomputer, and simulating the execution of the entire operating system.

Rosetta's job (like that of FX!32) is much simpler. The underlying host operating system provides an API identical to the one the non-native PowerPC code expects (they are both, after all, Mac OS X), so when the application makes a system call, or a call via an API which Rosetta knows is equivalent to a native API entry point, it simply passes on the call to the real operating system.

Most interactive applications actually spend the majority of their time executing code that's not actually part of the application, but the operating system: redrawing windows, rendering text, and so on. Because of this, such interactive applications are unlikely to suffer a performance penalty running under Rosetta.

This also applies to applications which make heavy use of 3D graphics: OpenGL is used to render these, and so the majority of the work will still be done by native code and the GPU of the graphics cards.

Limitations

From Apple's documentation, Rosetta's overall structure appears to be far simpler than FX!32's, more akin to Virtual PC's. Before executing a 'chunk' of code (probably a 4kb page), Rosetta first translates it to native x86 code before executing that. No mention is made of any profiling of the running code, or any further optimisation applied to it after the initial translation.

Blocks of translated code are cached, but it's not stated whether this cache is persistent. Implicitly, the translated code is discarded each time the application terminates, implying lengthy application startup times.

Applications which use linked libraries for which Rosetta cannot find x86 equivalents must run entirely in x86 mode, even if a Universal Binary (or fat binary, to use the old terminology) provides native x86 equivalents of the main application code.

In addition to these performance limitations, there are a few hard limitations. Naturally enough, PowerPC code for Mac OS 9 is not supported, and neither are kernel extensions. 64-bit code specific to the G5 will not be translated, and somewhat mystifyingly, AltiVec instructions are not supported at all, Rosetta's instruction set being modelled on the G3 rather than the G4 or G5.

Wait and see?

Will Rosetta allow Apple to transition as seamlessly as they hope? Will early adopters of the "new" technology be left distinctly unimpressed? Time will, as always, tell. At least they got one thing right this time: they picked a winner of a name (after, for obvious reasons, the Rosetta stone). It trips off the tongue, doesn't it? Rosetta... Rosetta... Rosetta...

Osborne Effect by Colin | Mon, 6 Jun 2005 21:18:30 | 0 comments

The Osborne Effect, named after its discoverer Adam Osborne (who was also arguably the inventor of the "portable" computer) is an effect which the marketing departments of technology companies need to be aware of, and possibly the prime reason for technology firms being secretive about their release plans, roadmaps and product cycles. I am, at this very moment, exerting the Osborne Effect on Apple Computer Inc, although you wouldn't think it to look at me.

Back in the early 80s, Adam Osborne was due to hit it big. Spectacularly big. Thanks to a marketing coup and the inclusion of a valuable package of bundled software, the briefcase-sized Osborne 1 was selling by the bucketload, and Osborne had big plans for the future. He'd planned to release a successor "Executive" model in the same briefcase form factor, and after that, a machine capable of running MS DOS.

With a roadmap like that, he should have been tripping over himself with investors. Instead, the company folded before it reached IPO. Counter-intuitive? Highly. I'll get back to that in a minute; first, we'll fast-forward to the present day.

I'm typing this on my 12" PowerBook G4. It's a lovely little machine, it's shiny and silvery and everything just works. But it's a bit underpowered. The Athlon-based desktop PC I bought in 2001 outpaces my 1GHz PowerBook, and in fact it still almost outpaces Apple's top-of-the-range PowerBook computers which currently clock in at around 1.67GHz. Intel and AMD-based notebook computers are far ahead of it in terms of performance.

What are my options? I could upgrade to a marginally faster PowerBook, but that would seem a large waste of money. I could buy a iMac G5 or a PowerMac G5, which would be adequate performers and certainly take the pain out of all those long compile jobs. But they're not very portable, so it's not viable to take them to work every day, never mind to the pub.

Instead, I choose to wait until IBM have sorted out a new lower-power, process-shrunk silicon on insulator version of the 970, and Apple have incorporated it into a notebook computer, at which point I'll buy that, and be happy. But in the meantime, I'm not buying a faster PowerBook or a G5 desktop system because I know that at some point in the not-too-distant future, I'll be able to buy what I really want.

While Apple are secretive about the development (or otherwise) of G5 PowerBooks, the existence of the corresponding desktop product gives us a clue to what lies ahead. Apple have inadvertently created a period of time in which I, as a (somewhat) loyal customer and enthusiastic exponent of their products, refuse to buy one of their products. And that, or so the story goes, is precisely what happened to Osborne.

Osborne announced the successors to the Osborne 1 at the height of the popularity of the machine. He was so successful at generating hype and technolust for the new products that the computer-buying population decided that it would be a far more sensible use of their cash to wait for the newer machines to become available, rather than acquiring an Osborne 1 and thus contributing to the company's research and development budget for the new machines.

Without enough cash flow to fund the R&D on the new machines, they were never successfully launched, leading to the collapse of the company and the disappearance into vapourware of the very product the public had been crying out for.

With a cautionary tale like that, is it any wonder that Uncle Steve is keeping quiet about when PowerBook G5s may be introduced? Personally, I'm happy to wait it out, safe in the knowledge that all the iPod-buying teenagers (or, perhaps more accurately, their parents) are funding the R&D of my next PowerBook. God bless their scrawny little hides and their angelic little lip piercings.

Epilogue

It's been recently brought to light that certain key aspects of the story of the Osborne Effect owe more to mythology than to reality. The company did indeed expecience a significant slump in sales following the announcement of the newer models, and it did indeed subsequently (but not neccessarily consequently) go bust. Competition from other vendors also played a significant part in the lack of turnover, and a few unfortunate management decisions (for example, the decision to spend $2,000,000 to make more mark 1s in order to make use of a $150,000 stockpile of unused mainboards) are more likely to be major culprits in the eventual demise of the company.

Regardless of which combination of factors, in what proportions, was responsible for the company's collapse, the Osborne Effect is still a tangible and concrete one. Far more tangible and concrete, in fact, than my speculated-upon PowerBook G5; which will, thanks to Apple's recent decision to switch over to Intel processors, never see the light of day.

http://oldcomputers.net/osborne.html
http://www.theregister.co.uk/2003/03/25/portable_computer_pioneer_adam_osborne/
http://freepages.genealogy.rootsweb.com/~tlosborne/Osborne/Osbornehistory/Adamosborne/adamosborne.htm
http://www.theregister.co.uk/2005/06/20/no_osborne_effect_at_osborne/

emulator by Colin | Fri, 3 Jun 2005 07:20:54 | 0 comments

"Emulator", meaning simply something which imitates something else, is generally taken to mean software to imitate a computer hardware platform, as covered elsewhere in this e2node. However, in the electronics industry, "emulator" (as an unqualified term) has a slightly different, and far more exciting specific meaning.

When designing a digital system which includes custom chips, there are a myriad of technical problems. Not least of these is the fact that, before being able to test your complete system (including system boards and software), you have to first finalise the design of your chip, then wait a few months (and pay about $1,000,000) for the chips to come back from the fab plant before plugging them into your system board and giving your software a go.

That's one hell of a debug cycle if you're still developing your chip. So, naturally, nobody does that. Instead, developers rely as heavily as possible on logic simulation of the current state of their work-in-progress chip. This generally works quite well for testing the design of the chip, and for testing the software. But because a software simulation is inherently, well, software, its interactions with the real world are limited.

Furthermore, software logic simulation is incredibly slow in comparison with real hardware, so if we were to allow our simulated hardware to interact with the real world (say via some I/O ports on the host computer running the simulation), it would do so incredibly slowly. If our device is supposed to generate sound, it would be so low that only whales could hear it. If it were intended to control a real-time process such as a chemical reaction, we'd probably have to evacuate the lab.

So, how do we let our chip design interact with the real world, in an almost-real-time nature? It depends on the scale of our chip, and what's on it. But the general answer is: we use an emulator.

What's that, then?

Simply put, an emulator is a large box, typically very expensive and power-hungry, which can be configured to behave like almost any digital circuit, up to a certain level of complexity and (typically very slow, but far faster than the equivalent software simulation) clock speed.

This allows developers to connect up their system boards and external peripherals to a device that will behave like the final chip (albeit more slowly) to test and debug the system, the chip design and the software. All in almost-real-time.

In the early days of VLSI, QuickTurn were the leaders in emulation technology, to the extent that "QuickTurn box" and "emulator" were almost synonymous. QuickTurn are now owned by Cadence Design Systems, and still making emulators, in competition with Aptix (who were recently bought by Mentor Graphics) and Ikos and a few others. Modern emulators range in size from the size of a deskside PC to a full 19" rack enclosure.

Architecture

If you're familiar with the concept of an FPGA, you're probably thinking "Hey, that sounds a lot like an FPGA." and you'd be right. For many small designs, a single FPGA can be used to emulate the entire design; making the task of emulation very easy and cheap.

But for larger designs, which will not fit in a single FPGA, we need an emulator; and modern emulators are invariable implemented as, in the main, an array or matrix of FPGAs with a configurable interconnection fabric, allowing a design to be mapped across multiple FPGAs. In addition, they typically contain RAM and other types of specific function hardware which are commonly found in designs but which are more expensive to implement in FPGAs than to simply include in the emulator, as well as a host microprocessor for high-level control, network functions and configuration of the FPGAs.

The other main component found on emulators is, of course, a vast array of wires, to be connected up to system boards, or any other external hardware necessary for testing of the system design.

The process of mapping a design into an emulator is extremely computationally expensive, and is typically handled by a dedicated cluster.

Value added features

One of the primary uses of emulators, as mentioned above, is in debugging: debugging the software, and debugging the hardware design. To facilitate this, most emulation systems have extensive debugging facilities. For example, cosimulation: the ability to communicate with a logic simulator loaded with the same design, such that a developer can examine the current machine state of a paused emulator, using the debug facilities of conventional logic simulation software. Debug breakpoints and signal value traces are also common.

Since these facilities add quite a lot to the complexity of the emulator, and will not necessarily be used in all emulator use cases, so vendors are starting to offer "replicant" emulators, to be used additionally to a full emulator. A replicant emulator lacks many of the debug facilities, and will of course use the same cluster to map the design to its FPGAs, so effectively doubling the availability of emulation for less than half the price more.