wget links for the video files of MIT-OCW SMA 5503

MIT’s open courseware has a number of courses which are of interest across areas. Few of these courses not only have the lecture notes, but also the video lectures recorded in MIT. Providing these courses in the public domain is a great thing that MIT is doing. It definitely will interest people like me who like to know how certain courses are taught in one of the premier education institutions. One of the courses, I recently chanced upon is the Introduction to Algorithms (SMA 5503). This course has the lecture notes also uploaded to the site.

As the bandwidth at home is not very conducive for streaming video, I decided to download the files. I did find a .torrent on mininova for this course. The seeds though, were stuck at 20% – not the best of the situation. So, I decided to download the courses from the source. The FAQ mentions how one can download the courses from OCW. Basically, one removes akamai (which seems to host the files for lesser latency in transmission), and points the URL to OCW. Below is the list of the all the .rm files for download. The list is for the high-bandwidth videos (220k real media files) and the lecture notes. You can save the links in a .txt file and use something like wget to download them to the local drive. I used something like this for wget:

wget -N -c -i ./links.txt –limit-rate=15k &

The links.txt is the list of the links



SouthIndies – an authentic South Indian cuisine restaurant with a difference

South Indies, south indian restauarant in Bangalore.

When you picture a South-Indian cuisine restaurant, an image of authentic South Indian decor, waiters who are dressed in a certain South Indian attire, cutlery which is very specific to this region, and then the lip smacking food. This is probably what comes to your mind. Discard all of those thoughts, except for the lip smacking food – and you can start reading about The South Indies.

This place is on the 100 ft. road in IndiraNagar, after the CMH road signal towards the Old Madras Road. Currently that road is being dug out for the metro, but even then I’d suggest you go there. The rating for the place -a neat 8 out of 10.

First, this place is not the average, rather hackneyed ethicity dripping restaurant. If it weren’t for the name, you would probably mistake it for a continental cuisine restaurant. The decor is chic, the place plays nice soft music, the cutlery is forks and spoons – but it is a completely South Indian cuisine restaurant. The beauty of the place (culinary beauty i.e.) is that it serves the food from all the 4 states in Southern India. When I went for the buffet, there was a keerai from TN, a palya from Karnataka, a koora from AP and rice dish from Kerala. And all of them (which is what I liked a lot) were very tasty. The curry from AP was guthi vankaaya (brinjal in a gravy – of course, the true guthi vankaaya is not a wet dish, but a dry one), the keerai was of palak (iirc), there was Cochin biryani and the palya was yam palya (iirc). If you think there are too many iirc, please check the time of this post :D.
I am not sure of the culinary origins of the appam, but do have the appam they serve. It is a little sweet, but with the stew they make along with it – it is very tasty (and given that I never liked appams that much, I think that is something !). And no meal is complete without a straaang filter coffee. The coffee is a little on the higher side of cost (70 INR), but it is good filter coffee. And given that I am a sucker for filter coffee, I didn’t mind paying that money for it πŸ™‚ The total cost for 2 people in a buffet was around INR 850.

The not so good parts of the place. The buffet is in a corner as if to hide it, the plates are heavy (or have I become weaker πŸ™ ), there could be a description of the dishes for the uninitiated, and they could give mor / majjiga at the end of the meal and importantly, the curd could be made to stay cold and hard – nothing beats that…slurp ! πŸ˜€

The theory of the problem with threads

The problem with threads has been very concisely explained in the famous paper[pdf link] of Edward A. Lee. Very simply put, the author argues that threads are a problem because they add non-determinism to an application, and that the programmer has to put in extra effort to control the non-determinism, while this should be the other way around. Quoting the author, Threads, as a model of computation, are wildly nondeterministic, and the job of the programmer
becomes one of pruning that nondeterminism. (..) I argue that this is approaching the problem backwards. Rather than pruning nondeterminism, we should build from essentially deterministic, composable components. Nondeterminism should be explicitly and judiciously introduced where needed, rather than removed where not needed

The author goes on to suggest few ways to allievate the problem

  1. Better software engineering process
  2. Use vetted design patterns for concurrent computation
  3. Using patterns which can be encapsulated into language libraries (for example, MapReduce)
  4. Extend the existing programming language with annotations to indicate concurrent compuations
  5. Using promises / futures as implemented in the E language (work on proxies of shared data instead of the actual)
  6. Using tools to determine if the existing code is indeed thread safe or not

The author then goes on to suggest an alternative to threads, as a system modeled closely like CSPs. In this model, the various components of the system are deterministic. The rendezvous director is the one which controls the nondeterministic part of the system. In such a system, the component is deterministic, but the merge is the one which is nondeterministic. In such a case, the merge block is where one can concentrate on to ensure that any rollbacks be transmitted back to the components. The discussion at LtU, has some interesting points (some of which are OHT for me right now).

This post of course is not deal with the problem of threads in detail. Rather, I want to concentrate on how the author presents a model of threads as a computation, and how one can clearly see the problem of nondeterminism creep. This makes is very difficult to reason about systems which are heavily threaded. As I am not aware of how to integrate the LaTEX plugin, I shall try to write the equations as closely to the document.

Let N={0,1,2…} be the set of natural numbers

B={0,1} the set of binary bits

B* is the infinite set of all finite sequences of bits

Bw =(N->B) i.e. it is the infinite set of infinite sequences of bits which give an output. An output of zero or one. Consider the Bw as that set of those bits which have some output (codomain in {0,1})

B** = B* U Bw i.e. B** is the set of all finite sequences of bits and those infinite sequences which have a finite ouput i.e. the finite sequences could either give an output or needn’t give any. This is the computing machine, which can potentially infinite inputs and potentially infinite outputs (remember it is the union between B* which is an infinite set).

Q is a partial function of values between B** and B** i.e. there can be values in B**’s domain which don’t map back to values in B** (that is what a partial function is). Simply put, this means that there are sequences (finite / infinite) which don’t have a solution in B**.

An imperative machine (A, c) is a finite set of actions and control functions. The set A is the set of actions are generally the instructions that are executed in a computation.

A program of length m is represented as p : N->A – a function between the number and set of actions. A way to say that for every N there is one program (actions) of length N. In simple words, a program of length m.

Now, that a program has been defined of length m, it is time to consider the state of the program as it executes (via a thread). bn+1 = p(c(bn))(bn), for bn being the state in B**. Here,

  • c(bn) gives the nth number to execute
  • p(c(bn)) the nth instruction to execute
  • p(c(bn))(bn) – result of this execution (apply the nth instruction determined by c(bn), to the bnth data to get the output of the execution)

Now, the author explains the actual problem with threads. For a sequential process b(n+1) is always defined for a given n. The output is always deterministic. But, if there are (say) two threads running concurrently accessing this data, then the equation becomes: bn+1 = pi(c(bn))(bn) for i in {1, 2}. (please read the pi as p subscript i). In this case, given the value of i, the next state is determined by either p1(c(bn))(bn) or p2(c(bn))(bn). So, even though, the next instruction as returned by the control function is known, the next state is nondeterministic because of the value of i that is picked up at that instance of time. And of course, if there are two CPUs (or cores) whose time slice is given to both of these threads, then the data access problems become compounded.

I hope I was able to explain the theory (I do know that it is not possible to explain theory withouth the right mathematical symbols, I shall fix that soon, once I get my head around either MathML or using LaTEX in HTML) as to why there is a problem with threads. The last equation of the program presentation is the crux of the complete problem. The bn+1 i.e the next stage is very clearly defined in the case of a sequential program, whereas in the concurrent program with threads, it is not defined. This essentially is the crux of the problem.

The author at the end of the paper tries to model the concurrent computation thus:

f: (T->B**) -> (T->B**). Here T is an ordered set of tags. The order of these tags can be determined by various factors like time, causality etc. In simple terms, based on some order within a set of tags, the next instruction to execute is picked, and that tries to find an output from a similar set of outputs – nondeterminism in its fullest.

Please let me know if I have made any factual errors in trying to explain the theory of the problem with threads. The idea behind the post was to make it easy for people to understand what those (sometimes scary) formal symbols actually meant.

Behind Deep Blue – an average read

Feng Hsiung Hsu’s book, Behind Deep Blue is the chronology of events that finally resulted in IBM’s Big Blue computer defeating Gary Kasparov. The text under the title (hmm, is sub-title the word for this ? or is there a better word ?) goes something likeΒ building the computer that defeated the world chess champion. If one were to not read anything more from this, then the book does justice. But, if you are expecting more details into the guts of it, then you might be disappointed. I give this book a 5 out of 10, and suggest you to borrow it if you can.

So, what is good with the book. The nice things about the book are when the author describes the design hurdles. Any large, parallel system throws up its own set of design hurdles. The author explains, sometimes technically (good if you are the technical sort), how they went about designing the system. How certain parts were set for the hardware and some for the software. There are also interesting notes about the various chess strategies, though he does not dwelve deep into it.

What is not so good about the book. Well, the book is more of a biography of the IBM Big Blue. Parts about its genesis, its design and then the calm after the storm. There are lots of personal details, including the author’s collaboration with people in CMU and then in IBM. These details, interspersed between the technical sections of the book, can sometimes catipulate the reader’s interest. I thought, lesser content regarding this, and more regarding the system itself would have made the book a lot more interesting.

This book made me wonder, where does one draw the line when trying to explain a system. Building a large parallel system is a challenge, and most people can’t fathom the challenges faced in designing something as large as the Big Blue. So, if one were to explain to a layman, there are lots of parts – the interesting ones, which might need to be skipped. It is an interesting thought, and I shall try to write about this some other time.