If you have ever worked on placement or floorplanning, and probably some other areas of EDA, then you will have heard of "Kernighan and Lin". It's a partitioning algorithm. You might not even have realized that the Kernighan of Kernighan and Lin is the same person as the Kernighan of Kernighan and Ritchie, or K&R, the standard reference work on the C language.

Brian Kernighan has just come out with a book, Unix, A History and a Memoir. He was one of the people who was involved in the early days of Unix and C at Bell Labs, as well as developing graph partitioning algorithms for his PhD thesis.

Bell Labs

Bell Labs still exists, although today it is known as Nokia Bell Labs (it was part of Lucent until Nokia acquired Lucent). The main lab, and the one where all the computer science was done, was at Murray Hill, New Jersey, not far from New York. Perhaps most famously for our industry, John Bardeen and Walter Brattain invented the transistor in 1947. A year later, William Shockley invented the junction transistor, which was actually manufacturable. That same year, 1948, Claude Shannon published A Mathematical Theory of Communication and invented information theory.

Shockley, Bardeen, and Brattain won the 1956 Nobel prize for physics for their transistor work. Overall, people at Bell Labs won nine Nobel prizes and four Turing Awards. That's more than most countries.

Brian's Books

Brian himself is probably best known as one of the two authors, along with Denis Ritchie, of the book The C Programming Language first published in 1978. I remember reading, but I can't find it now, that the book was only expected to sell a few thousand copies and so it was priced high...especially given that it is just 228 pages long. The current (second) edition is 272 pages long and has a list price of $67 (although you can get it for a lot less). In fact, the book has sold literally millions of copies and has been translated into over 20 languages. The book is often known as "K&R" after the initials of the two authors, and in the early days of C, the language described in the book was known as "K&R C".

It wasn't his first book, which was The Elements of Programming Style published in 1974. This was co-authored with Bill Plaugher. They based the book on the legendary Strunk and White book The Elements of Style (first published in 1920 and still in print). In particular, they used the idea of showing examples of bad writing/programming, and the cleaning it up and showing good writing/programming.

One thing that Brian came up with and that was introduced to the world in The C Programming Language introduced was the "hello world" program. Pretty much any book on programming in any language starts with this. It is a program that simply writes out "hello world". But Brian first introduced it in a 1974 internal memorandum. It even has its own Wikipedia page. As they put it in the first edition of the book:

The only way to learn a new programming language is by writing programs in it. The first program to write is the same for all languages: 

Print the words
    hello, world

This is the basic hurdle; to leap over it you have to be able to create the program text somewhere, compile it successfully, load it, run it, and find out where your output went. With these mechanical details mastered, everything else is comparatively easy.

Kernighan and Lin

I first came across Brian's name when I was working on some EDA tools at Edinburgh University during the time I was doing my PhD. I was also employed by the university, so despite the fact that my PhD was on operating systems and distributed file systems, I worked on some EDA tools, too. Working on EDA tools turned out to be more significant for my career than my thesis topic. Brian's PhD thesis, and paper with Shen Lin, were on a graph partitioning algorithm. The basic problem is to partition a graph into two so that as few edges as possible cross the partition. The algorithm is usually just called "Kernighan and Lin".

I implemented and used the algorithm to create a program that assigned gates to TTL components. In that era, before anyone in academia knew anything about integrated circuits, designs were done using the TTL 7400 series, originated by Texas Instruments. Individual chips would contain things like six inverters or three 2-input NAND gates. It would make the board design more compact to minimize the signals that needed to go between chips, meaning that the other signals could be very locally implemented.

Here is Udacity's 2012 video on the Kernighan and Lin algorithm:

 

The basic idea was to use Kernighan and Lin to partition the design into two halves, then partition each half into two, until the partitions were small enough to be assigned to a single chip. Early VLSI placement algorithms for physical design took a similar approach. You end up with the most tightly connected components grouped together, and relatively few long wires. Or as Wikipedia puts it:

The algorithm has important applications in the layout of digital circuits and components in VLSI.

In his book, he gives a lot more background on coming up with the algorithm. One thing that he and his colleagues never succeeded in doing was to prove that their algorithm was optimal. The concept of algorithmic complexity was in its infancy, and concepts like NP-completeness did not exist. In 1971, Stephen Cook formalized them in a seminal paper The Complexity of Theorem Proving Procedures for which he would later win the Turing Award. Proving that Kernighan and Lin, and other similar problems, are optimal is an open question, but almost everyone believes that there is no algorithm that is optimal beyond the brute force approach of trying every possibility. For more details, see my post What Does P≠NP Mean?

Meeting Brian

I first met Brian during my time in Edinburgh. But I met him in Canterbury, which is in Kent, to the south-east of London. (Yes, the place where the pilgrims in The Canterbury Tales were traveling to from an inn at Southwark.)

I traveled there by train, and I don't remember any baudy tales being told. I was going there for an operating system workshop of some sort, and Brian gave the keynote on Unix. I think that the seventh version had just been released and he gave a little of the history of the development and a lot of the details of the new release. Unix was not yet widely known, so he spent some time describing its simplicity and comparing it to IBM's TSO (Time Sharing Option). As I remember he put it:

Using TSO is like kicking a dead whale along the beach.

A mutual friend introduced me to him and had a brief conversation with him, saying I'd actually used Kernighan and Lin in earnest in a real tool, which he found amusing since the original graph partitioning was purely theoretical.

I didn't expect to meet him again anytime soon, but when I decided to come and work in the US for a couple of years (yeah, I'm still here, the best laid plans, etc) I interviewed at a number of companies: Bell Labs and Digital Equipment on the east coast, Intel and HP on the west coast. At Bell Labs, one of my interviews was with Brian. I don't remember what we really talked about, although I remember it was more of an hour-long chat ranging over lots of computer science topics, rather than a formal interview.

I never found out whether Bell Labs were going to give me a job or not, probably not. The reason was that I interviewed at one other company on the west coast, VLSI Technology. They leveraged the fact that they were a startup and could move faster than more bureaucratic large companies: they gave me an offer before I left the building. I decided working for VLSI, at the time a startup with about 50 employees, seemed like it would be fun for a couple of years (remember, I only planned to come to the US for two years, since I figured a Silicon Valley job would look good on my resume when I got back to Britain), so I accepted my offer there. As it happened, VLSI had assembled the best team of EDA developers in the world, and like everyone else who worked there, I learned an incredible amount in my time there.

Unix

The bulk of Brian's book is a history of Unix. I consider it the most important operating system of all time. Your iPhone runs a version of Unix. Android is a version of Unix. Linux is a version of Unix, and runs most server farms and all supercomputers. I'll write about that later.

 

Sign up for Sunday Brunch, the weekly Breakfast Bytes email.