Wednesday, May 27, 2015

Dirty Trick #11 -- Master Key

The combination locks that were checked out to students in my junior high and high school were outfitted with a cylinder that would accept a master key.  This was undoubtedly a great convenience for the custodian, in case access had to be gained without the student's participation.  It immediately occurred to me that I would have great power over my fellow students if I possessed a copy of that master key.

I had no thought of "borrowing" the master key from the custodian, but I did consider making one.  Before I started high school, somehow one of the high school locks was added to my collection.  I used an assortment of my father's tools to destroy enough of the lock to remove the cylinder.  And during the same time, I obtained a blank of the right dimensions from the local K-Mart.  It only remained to measure the tumblers and shape the key so that it moved the tumblers into the right alignment..

That is where I lost confidence.  I had only one blank, so I didn't dare make an error.  I had the cylinder out of the lock, but I didn't want to take the tumblers out of the cylinder, for fear that I would not be able to reassemble the precious cylinder and test my creation.  If I had had 10 blanks and 2 cylinders, the outcome might have been different.  As it was, I abandoned the project after taking one small nick out of the blank with a file.

No matter.  It turned out that the idea of a master key was just as good as the real article.

The spring of my sophomore year, I was standing near Kathy Humphries' locker and chatting with her before fourth period.  One of a group of bullies standing nearby reached into Kathy's locker, took out a package of Twinkies, put it in his own locker and slammed the door before we could protest.  We both demanded the Twinkies back, but the boys laughed and went off to class. 

I vowed revenge.  I had noticed that the boy had a baseball glove in his locker, and I imagined there were other valuable items in there as well.  I returned before 7th period and tried to get the baseball glove in order to force a swap.  But the bully saw me coming and guessed my intent.  The locker door was closed before I could reach inside.

It happened that that day was a Friday.  I returned to the school on the next day and used my usual trick to pop the latch on the cafeteria doors at the west side of the building.  Soon enough I gained access to the math wing, and went to the right locker.  With a swift kick, my hiking boot knocked the entire handle off the front of the locker. 

I had observed another locker whose handle had been broken off by accident, so I assumed it would be easy enough to repair.  I examined the locker handle, and found that it had been held in place by two small machine screws.  My blow had caused both to shear off near the head, but neither the locker nor the handle was damaged.  All I needed was two replacement screws, and the locker would be good as new.  I backed out the shafts of the headless screws and picked up the heads. I put all these in my pocket for later comparison.

It was then easy enough to help myself to the locker's contents.  But I didn't want to be found with stolen property in my locker.  That would never do.  I needed a safe place to store the loot that was not incriminating.  I immediately got the idea of putting the stuff in the lost-and-found.  I took the glove and a cap and a few smaller items, and went down to the principal's office.  I used my latch pick to open up the main door and then went into the closet that held the lost and found.  I burrowed down in the pile of forgotten clothing and nested the goods near the bottom of the cardboard box.

Then I went down to McGuckin's Hardware, and found a match for the broken screws in thread size and length.  I even had the good fortune to find ones with hexagonal heads, just like the ones I'd broken.  I went back to the high school, repaired the locker handle and left.  So far, so good.
---***---   ---***---   ---***---   ---***---   ---***---   ---***---   ---***---   ---***---  

On Monday, I was met at my locker by a very angry bully-boy.  Angry, but respectful, lest he should make me decide to return his property never.  He demanded to know if I was responsible for the disappearance of his baseball glove, and wanted to know how I had done it.  I told him I had made a master key that fit all the locks in the building, and he wasn't going to get his glove back until he returned the Twinkies.  He said he didn't have the Twinkies any more (presumably having eaten them).  Too bad.  (Conversations were short, because the halls cleared out in a hurry when the second bell rang.)

A short time later, I received a note that summoned me to Millie Beavers' office the following period.  Millie was the head of the math department, and also was responsible for managing the lockers in the math wing.  When I showed up in her office, she put out her hand and said, "Okay, where is it?"  (I was taking independent study math which she supervised, and her tone was normally much more cordial.)  I was forced to explain that there wasn't any master key, and how I had obtained access to the locker by breaking off its handle.  When asked about the loot, I said I didn't really take it -- I had just put it in the lost-and-found.

That was the end of it: I received no punishment; the boy reclaimed his stuff, and Kathy never did get her Twinkies back.  In retrospect, I suppose Millie was smart enough to let the master key story stand. Revealing that a locker handle could be sent flying by a sincere glancing blow would have precipitated general mayhem.  So that was our little secret. 

From the bullies' perspective, however, the idea that I had made one master key certainly meant that I could make another.  Bully-boy and his chums treated me and Kathy with proper respect for the rest of our time at Boulder High.

Monday, September 1, 2014

Dirty Trick #10 -- Applied Physics

By the time I was in high school, I was already a feminist.  My mom -- being then the president of the Boulder chapter of NOW -- had made sure of that.  But she had also moved beyond believing (as some feminists did) that common courtesies -- such as holding doors and allowing ladies to enter first -- were symbols of sexism. Rather, she treated them as a mark of respect that was her due.

Two of the young ladies in my physics class, Kathy and Alison, had decided at this time that they were feminists, but they were still on the previous page.  I would often arrive at the dual doors to the math/science wing a few moments ahead of them, and began holding the door open for them.  Whereupon, they would make an elaborate show of opening the other door for themselves and passing through.

After the second or third occurrence, I decided to take advantage of their predictability -- and I knew just how to do it:  Some time before, I had noticed that the left-hand door was hard to open, and took a long time to close.  An  examination of the door-closer mechanism revealed a set screw. Using my pocket knife, I loosened the set screw and tried the door.  It opened easily, and closed more rapidly.  "Ah, hah!" I said to myself, "this must be an air bleed, intended to control the speed at which the door closes."  But it could also make the door hard to open. [cue ominous music]  I had thought that door-closers contained a one-way valve that would always allow the door to open easily: the air bleed would only control the speed at which the door closed.  But this one either lacked such a valve, or that valve had long since failed closed.

The next day, I made an extra effort to arrive early, took out my pocket knife and twisted the air-bleed screw on the left-hand door-closer firmly into its seat.  No air bleed.  I tried the door and it swung open a few inches.  It would have taken a team of oxen to open it any wider.  Perfect.  People were starting to arrive, so I held the right-hand door open for them.  Those exiting the wing were obliged to duck around the mullion. 

Right on cue, Kathy arrived.  Following the standard script, she went over to the left hand side and tried the door.  No dice.  She gave me a look that would melt steel as she swept through the right-hand door.  Mission accomplished.  I put the set screw back to its previous position, and joined the physics class.  Kathy avoided the left-hand door for weeks....



Sunday, March 16, 2014

Dirty Trick #9 -- Office Space

One year on the 31st of March, I took care to put a 6mm hex wrench in my pocket before setting out for work.  After most people had gone home for the day, I went to the multi-purpose room and helped myself to a spare piece of cubicle wall.  I carried it up to my boss's cube and installed it in place of the gap that formed the entrance.

The next morning, Mikel strode down the hall, cut a quick dogleg to the left and ran smack into the newly-installed barrier.  I wasn't there to witness it, but he related the story to me later with a chuckle.

Thursday, May 23, 2013

Dirty Trick #8 -- Remote Control

In junior high, I was already doing my own bike maintenance.  From time to time, it became necessary to transport a disabled bike down to The Spoke in the Table Mesa Shopping Center.  What better way to do so than to push the stricken bike while riding on another one?  A bit of experimentation revealed that grasping the second bike across the handlebar stem afforded me complete control over where that bike was headed.

My new skill came in handy a short time later.  There was a bully that went to the same junior high, and rode his bike to and from school along the same route through the Bureau of Standards.  It was not a through street for cars, and crossed some undeveloped grassland for about an eighth of a mile.  Away from observing motorists and residents, he felt like he could get away with anything -- such as shoving me off the roadway or trying to put sticks in my spokes. 

The day he came up and prepared to force me off the road, I simply reached across and placed my right hand on his handlebar stem.  It didn't take him long to realize that the situation had changed completely.  His nasty/smug look disappeared almost instantly.  After I plotted a new course for him that veered gently away (well, maybe there was a rock or two on the shoulder that he had to avoid), he left me alone on that day and ever after.

Dirty Trick #7 -- Making Tracks

My bike route to and from school took me across the Bureau of Standards.  The sidewalk entering from King Avenue went through a curb cut and emptied into a parking space that was clearly marked as No Parking, with yellow hatching throughout.  But there's always someone....

The day I found a blue Mustang hatchback blocking my path, I decided to leave the driver a message.  I took the front wheel off my bike and looked around for a handy mud puddle.  After coating the full circumference with black mud, I went back to the Mustang and drew a tire track up the hood, up the center of the windshield, over the roof, down the hatchback and onto the street.

It's an open question whether the driver got the message, but I don't recall finding that particular car blocking my path ever again.

Sunday, November 4, 2012

Quality Only Breaks Once

In a recent party, we were discussing the poor quality of most kitchen appliances.  The topic began because a friend (Mike) complained that he was on his third or fourth bread machine.  I jokingly suggested that any appliance with "For Household Use Only" stamped on the bottom was a piece of junk, meant to hold together only long enough to get it off the showroom floor.  This was called to mind by my seemingly solid electric pasta machine, which nonetheless stopped working after it had produced a few dozen batches.  It provided the information needed to translate "For Household Use Only" correctly.

The first Kitchen Aid stand mixer I had stopped working after about a month of use.  It came with a lifetime warranty, so I took it to a local appliance repair center.  There, they replaced the broken annular gear (free of charge), and it has worked fine ever after -- providing almost two decades of faithful service before I gave it to my niece.  I joked that it came with a cheap, nylon annular gear, but when I took it in for service, they replaced that one with one of solid brass.

Whether or not that's true, it suggests a business model that could be quite successful:  Have a production model of your product that is manufactured rather cheaply.  Nonetheless, deliver the standard model with a lifetime guarantee, and charge a bit extra because you can claim superior quality.  The trick is, that most owners will not use the product nearly enough to discover its flaw.  Those who do will hopefully return the unit for service or replacement.  The replacement unit or parts are top quality.  If the unit ever comes in for repair, *all* of the cheap critical components are exchanged for top-of-the-line replacements.

Among those who actually use the appliance it will eventually earn the reputation for high reliability, while among the rest the assertion will never be tested.  Meanwhile the difference in price between what can be charged for a top quality model and the cheap models you actually produce is almost pure profit.  As long as the amortized cost of repairing (or replacing) the models which do come in is less than that margin, you're money ahead.

I suppose that selling crappy software along with the promise to fix any bugs that may arise follows pretty much the same business model....

Monday, October 15, 2012

On Parallel Programming

"Sequential programming is really hard, and parallel programming is a step beyond that." -- Andrew Tannenbaum, USENIX 2008 Keynote Speech

A colleague quoted this in a recent email, and I feel obliged to respond to it.  From practical experience, it is easy to nod in assent and let it go at that.  An application that is not designed to run in a multithreaded environment is quite likely to fail when simulated or actual parallelism is added.  And even some applications that are carefully designed to run under parallel execution fail because the designer or coder neglected an important detail.

 But the fact that I am working on a programming language that is intended to make the job of programming parallel applications easier means that I cannot agree with this assessment wholeheartedly.  Of any profession, the promise that automation can rescue practitioners from tedium dangles closest in front of software engineers.  Early programmers struggled with machine code until the first symbolic assembler was created; later coders strove with assembly language until usable high-level languages were introduced.

Even though the concepts used to produce code that will run correctly in a parallel processing environment have been around for decades, it is reasonable to assume that parallel programming is still in its infancy, and that software tools will again come to the rescue.[1]  The main reason is that multicore processors have only become common within the last half-decade or so.  The redundant cores are currently an underused resource, but already applications must find ways to utilize this resource to remain competitive.

As with any in the technology used to program computers, it will take some time for new programming models to become widely used.  There is a lot of legacy code and many entrenched coders.  The old code bases may need to be recoded or encapsulated to run efficiently in the new environment.  Experienced coders will have to learn a new skill set to be effective with new coding paradigms.  However, we have ample examples from the past in which this paradigm shift has occurred.  The new programming model not only shapes how software is written to run on existing machines, it affects how the machines themselves are designed.  Hardware advances impinge upon the tools and programming model used, and the cycle continues.

In the present turn, the presence of parallel hardware is the motive force; tools and especially the programming model are obliged to catch up.  The programming model is central to the discussion, and carries the burden of the perceived difficulty.  Serial programming is hard, but in my view it is harder than it needs to be.  If the process of creating a parallel programming involves first writing a serial program and then parallelizing it, it is no wonder that parallel programming is thought to be more difficult.  But the excess complexity of serial programming and extra step of parallelization can both be dispensed with.

The inessential complexity in serial programming arises the expression of a linear flow of control.  Early single-processor machines could execute only one instruction at a time, so a complete ordering of the instructions fed to it was an accurate representation of what the machine was doing.  The state of the machine between each instruction could be predicted with precision.

With the advent of superscalar architectures, however, the connection between instruction sequence and execution sequence became more tenuous.  Superscalar architectures can dispatch more than one instruction at a time, perhaps blurring the exact state across several instructions.  Such processors contain internal circuitry to ensure that the observable state of the machine matches what is expressed by the code.  A hazard occurs when two simultaneously-executing instructions intend to read and write (or both write) the same register or memory location.  The circuitry enforces a stricter ordering of the execution of instructions when hazards are present.  A programming model that fundamentally assumes parallel execution would not require this extra circuitry.

If, in the absence of hazards, instructions can be executed in any order, then it becomes clear that the serial expression of execution carries extra information that is not essential to the expression of the algorithm.  It is convenient to list the work that needs to be done linearly.  But often, the exact ordering of the statements in a program is incidental.  I use this flexibility to group statements that are related and thus enhance the readability of the code.  But the very fact that I can do this reflects the presence of ordering information that is unimportant.

In fact, some compilers will perform instruction reordering to reduce execution time.  They perform a dependency analysis among the variables described in the program, and determine the order in which operations must be performed to preserve the original intent.  In effect, that optimization throws out the most of the ordering information supplied by the programmer, preserving only those partial orderings which are essential to the algorithm.  It then builds a new total ordering from scratch.

Given that much of a serial program representation is incidental, we are encouraged to consider a programming model that avoids this overhead.  The language must provide the means to express important sequence constraints while ignoring or discouraging the inclusion of incidental ordering information. 

It turns out that a number of programming languages already exhibit this property to some extent.  The goal-dependency representation in makefiles is a familiar example.  The goals express the dependence of a given target on a number of source files, which is in effect a sequence constraint:  A given source file must be present before the target can be produced.  In a serial processing environment, a feasible total ordering can be derived from an initial goal and the constraints provided.  In a parallel processing environment, each goal represents a task; a task can be added to the ready queue as soon as all of its constraints are satisfied; any available processor can execute any task from the ready queue at any time; completion of a task changes the state of each file touched by the task.

This declarative (as opposed to "procedural") style of programming is represented by many languages -- some of which have been around for decades.  Prolog is an early example, XSLT a more recent contribution.  What these languages have in common is that -- at least at a high level -- they specify the "what", not the "how".  This approach allows the implementation considerable lattitude in scheduling tasks so long as the explicit sequence constraints are met.  In fact, the algorithm for executing on a single processor is just the degenerate case of the algorithm used for parallel execution.

If declarative languages are more suitable for parallel applications and implementations exist today, why haven't they enjoyed more widespread use?  One reason is historical: When declarative langauges were introduced, available computers were almost exclusively single-processor.  Quite a bit of overhead is involved in scheduling the tasks to be run, and all of this had to be simulated in software.  Once scheduled, the tasks were run on a single processor, so no speedup was possible.  It was impossible for an algorithm specified in a declarative language to run faster than the same algorithm specified in a procedural language.  Hence, declarative languages were labelled as "slow" and dismissed.

With an abundance of processors sitting idle and hardware-assisted task scheduling, the landscape has changed.  Perhaps it is time to give declarative programming another chance.  In future posts, I'll provide a more thorough review of existing programming languages, with an eye to their applicability in a parallel execution environment.  Then if need be, I'll decribe the characteristics of a new language that is well suited to bridging the gap between serial and parallel programming.

[1] Myths About Scalable Parallel Programming Languages Part 6: Performance of Higher-Level Languages