What is this page?

I find myself often telling people about my past and present research results. For a long time, I thought that it was tacky to toot my own horn. Either people should know what I have done or the historians will sort it out. I finally realized that it is very unlikely that anyone will ever wrote a book about me. I also realized that there are people who might want to know what I have done. I may not be famous but I have lived by my own rules and perhaps my life might be an inspiration to someone out there.

My Story

Most people like to separate their research life from their personal life. I btoh agree and disagree. My personal life and information is not for public perusal. On the otherhand, as a member of the human race my personal and academic are intimately intertwined. My research results and insights occur in all aspects of my life and there is a desire to publicsize them all. Luckily, html lets one easily highlight publications and other links that visitors may want to quickly find. One does not have to read the details in order to find the good links quickly.

I am married and have three children (two girls and a son). My kids have had a huge impact on my life and research. Pre-family allowed me to work long and hard on a single problem. Kids at home demands that I reserve evenings and weekends for real life.

My Undergraduate Career -- Queens College

I graduated from Queens College (New York) in 1976. My major was computer science and back then, this was unusual as very few places offered degrees in CS.

My mom worked at Queens College and she also went back to school. In 1976 we both graduated

In my senior year, I also worked for a startup company they wanted to build an on-line health testing service. The idea was that one would not have to see a doctor for their annual health checkup. Instead, one would take a set of medical tests and the result would be either a recommendation to see a doctor or just come back next year.

I wPhoney Programmingrote a multi-taking operatng system for a Data General Nova minicomputer and a Control Data Eclipse minicomputer.

We were bought out and disbanded. This gave me a healthy distrust for big industry. I was already going to NYU for my master's. But I found it hard to give up industry. I did and am glad I did. However, I advise all my students that they can take off a year between

Of course the world is different now, but I wanted to do research because I wanted to do research not because I thought it was a great life.

My PhD Story -- Courant Institute (NYU)

The Courant Institute at New York University was my home for my graduate career. It was a great place to do a PhD. Despite my leanings towards systems work, Courant gave me a healthy respect for applied mathematics.

Between Master's and PhD I took a multimonth bicycole trip through Europe. I highly recommend taking time off to recharge batteries before the long haul.

NYU-Ultracomputer. Combining fetch-and-add in Omega network. The main idea is as follows. Suppose there is a set of processors and a set of memory modules with a multi-staged interconnection network. Back then, this was one reasonable way of thinking about a parallel machine. Today, we assume the memory is near the processor and all together they form a non-uniformly accessed shared memory. Today, it mught be more reasonable to assume that the processor and memory are a single unit and the netowrk connects the disks.

When multiple processors try to acess the same variable at about the same time, their requests will meet at some switch within the network. Usually, this will mean that one request waits while the other continues. The innovative idea is to combine the two requests into a single one which gets forwarded. On the return the single response gets split into two separate responses. ((I need a link here to a couple of Ultracomputer papers))

Butler Lampson claims that ever successful engineering project must "do one thing right" My take on this is a bit different. Every project needs to have one thing interesting. One thing that captures the imagination; one thing that every team member brags about. This helps everyone do their mundane routine work in a high quality fashion. Combining Fetch-and-adds in a network is an idea that can excite a whole project even if combining rarely happens and is only a small part of the project.

Post-Doc Story .

Balanced Sorting Network. This occured during the era of Algorithmic Animation -- the belief that students and researchers can get a better understanding of how an algorithm behaves by seeing it in action. There is a movie, entitiled "Sorting out sorting" that I watched in the back of a large auditorium. Paying only partial attention, quick sort appeared as if it had the following properties: compare the leftmost item with the rightmost one and switch if they are out of order. Do the same for the second leftmost item and the second rightmost item. Then after doing this for the n/2 pairs, do the same for the left half and the right half recursively. This makes a great parallel algorithm that takes only log n time with n/2 comparitors. Unfortunately, it does not sort.

Anti-aliased parallel programming.

CMU Research Scientist Story

Carnegie Mellon University

Amortized cost analysis: The skiing analogy

Program Visualization

Israel Story

Makbilan

Gang Scheduling

Dror Feitelson, was my most productive students as well as the most organized. We wrote a bunch of papers together. I need to give a more detailed review of them. But for now, use this link to see papers.

Free-Space Optical Interconnect

Self-scheduling Load Balancing

Given a shared memory parallel processor, set of parallel tasks and a set of processors, an a round-robin scheduler nifty way to balance the load is to allow a load balancing task to execute with probability 1/L, where L is the length of the task queue. A load balancing task chooses some other processor at random and balances the load between the two. What is nice is that if the task queues are short, then load balancing is performed frequently (if one processor has 100 tasks and the other 5 processors have only one task, then it is important to balance often, but if the other 5 processors have 98 tasks, then balancing should be done infrequently. This is explored in "A Simple Load balancing scheme for task allocation in parallel machines" with my student Miriam Slivkin-Allalouf and my collegue Eli Upfal. (BibTex)

Race Detection

Detecting race conditions in parallel programs has been the subject of lots of research. A very early work in this area was published at an obscure conference in Israel. It is well referenced although not too many people every saw the original. It makes use of a Hebrew-English labelling system -- the English labelling numbers the nodes of a tree in breath-first order from left to right whereas the Hebrew labelling numbers the nodes from right to left. The combined numbering makes it easy to detect simultaneous, unprotected access to shared variables. The paper is entitled "Tools for the efficient development of efficient parallel programs" with my student Itzhak Nudler (citation)

MIT Story

Next Generation Parallel Computing

Start Voyager

Job Scheduling

Malleable Caching

Column and curious caching. Ed Suh's work on adaptivity. Enoch's work of associative paging strategies

Pervasive Computing

There is so much to write here. There have been a bunch of projects that did not get published, but the results will be written up very soon.

This section is about what I have been doing recently. It should be clear that I changed fields. It is such a hard thing to do. Parallel processing or supercomputing is easy for me since I know the field, know people and have friends. I know what works and what are the challenges. Switching fields means having to learn all this stuff once again. But switching to a field that is still new and evolving is even more difficult.

I feel like I am old enough to take a huge risk. I have not jumped into the field fully -- I rarely go to Pervasive computing conferences nor do I often read papers in this area. I do read some but do not know the literature. This is a very risky thing to do. I do it because I want to see the challenges on my own. I do not want to be influenced by others until I have a good understanding of the challenges and opportunities. Of course, being at MIT means that there is a lot of work done here and there are numerous visitors coming through and numerous students who have studied the literature. So I am not completely disconnected. As my understanding improves, I do more reading.

There are many challenges that I believe are in my ability to address -- if not to solve then at least to make progress. Of particular interest to me is the "grandma debugging" problem. In a world infested with digital wireless devices, the number of things that can (and will) go wrong is enormous. There will be little support and lots of unexplained behaviors. I want to make living in such a world possible for grandma and grandpa and I want to get this done before I will need to use it.

Core Router
Speech Controlled Animation
Pen stroke detection via PDA camera
Bluetooth group key
OKNet Kiosk
Phoney Programming

Larry Rudolph Autobiography

Larry Rudolph's Academic Autobiography

Related Outside Links

Some more links