Recent content on Saurabh Jha
In this article, I describe how I made the transition from working on web applications to working on compilers. I’ve written this as a chronology. The chronology has gaps as it’s not a continuous timeline. I use some terminology that might be unfamiliar. I used it to add some flavour to my descriptions and I hope it won’t deter you from reading. October 2019 I decided that I want…
In the last article , we looked at expressing matrix multiplication using rank one matrices. In this article, we will study LU factorization using rank one matrices. Prerequisites We are assuming that you are familiar with linear algebra corresponding to a typical undergrad course. In particular, we are assuming that you are familiar with Gaussian elimination and LU factorization. Running example…
Matrix multiplication is a fundamental operation in many areas of computer science. In this article, we will explore a new technique of doing matrix multiplications. We will first get some intuition by going through some examples. We will then formally prove that the new technique gives the same result as the standard matrix multiplication. Finally, we will discuss its possible applications.…
In this article, we cover concepts from the second lesson of the advanced compilers course from Cornell. However, the specific algorithms discussed in this article are different from the ones discussed in the course. Introduction To execute a program written in a high level-language, we first need to translate it into a processor-specific machine language program. One way to do this is to first…
Introduction Once we have tokenized some program text, we need to check whether the tokens are in the correct sequence. For example, which of the following token sequences are valid? Tokenization of “32 + 4”: “<number, 32>, <+, +>, <number, 4>”. Tokenization of “+ 32 4”: “<+, +>, <number, 32>, <number, 4>”. Regular expressions are not powerful enough…
The first thing we do when we try to understand some program text is to divide it. For example, “12 + 34” can be divided into “12”, “+”, and “34”. If we want to include spaces, we can divide them as “12”, " “, “+”, " “, and “34”. Or if we are crazy, we can divide them as “12 +” and…
In my previous post , we stated that the goal is to use an array language to explore the problems of implicit parallelism. To get started with that, we need an infrastructure on which we can test our ideas. Specifically, we need to design and implement an array language before we can tangibly do anything. We are going to start easy and add features as we go along. In particular, we should keep…
Over the past several weeks, I have been thinking about this problem: if we have a programming language where the only permissible data type is an array, can we implicitly parallelize that? The idea of implicit parallelism, as I understand it, is that the compiler automatically creates threads and maps those to the program without the programmer specifying it. This can become an important problem…
This paper was written by the great Edsger Dijkstra. Before reviewing it, I should point out a couple of quick facts: It was published in SOSP 1967. It predates UNIX and C. This paper describes a multiprogramming system named “THE”. It’s main contributions are: A demonstration of the concept of software layering and how it leads to better verification and testing of a system. The…
These are my thoughts on the classic paper “End-to-end Arguments in System Design” written by Jerome Saltzer, David Reed, and David Clarke. It’s a very old paper; the version I read was published in 1984. The paper argues against implementing functionality at lower levels of the system. It appeals to application requirements and argues for moving a function upwards in a layered…
I taught myself some concurrent programming lately. I did it as part of my operating systems studies. In this essay, I will illustrate it using an example problem. I will be illustrating concurrent programming using operating system primitives. [1] There are several different ways to do concurrent programming that does not involve interacting with the operating system kernel. Even if we restrict…
I am involved in some official project where I got a chance to set up web infrastructure. This was the first time I did any kind of system administration work so it has been an adventure. Here are some lessons I learned as I did and continue to do this work. Read the fine manual (RTFM) Be ready to invest lots of time reading up documentation. For web applications: Read up on your hosting provider…
I got interested in systems programming due to an assignment at work that involved sockets. I got curious about what could be happening behind such an interface. I started studying the python interface to sockets. It was very high level and I did not learn much. So, I started studying the UNIX interface. With UNIX, I got overwhelmed and painfully realized that I won’t be able to understand…