Sunday, April 8, 2018

On even and odd numbers, and kid's questions

Kids ask the best questions. Unburdened by prior knowledge or assumptions, their questions are driven by pure curiosity and a deep desire to learn something new. As adults we can learn a lot from how kids ask questions and seek knowledge. And we can also learn or strengthen our understanding of a particular topic by answering kids questions.

For example, my son asked me a question about even and odd numbers, and why we get an even number when we add two even numbers or two odd numbers, and an odd number when we add an even and an odd number. Because this knowledge is drilled into us since our younger years, we stop wondering why.

Intuitively we know the proposition is true, and we can cite a couple of examples to prove it to ourselves. For example, adding 2 and 4--both even numbers, gives us 6, also an even number. When we add 3 and 5--both odd numbers, we get 8, which is an even number. If we choose a mix of an even number and an odd number and add them, we got an odd number. For example, adding 2 and 3, we get 5, which is an odd number. It seems that our intuition is onto something. Sometimes intuition leads us astray, and reality is reflected by something non-intuitive. The theory of relativity—both special and general, and quantum mechanics for example offer non-intuitive description of reality and how things work.

The addition examples above are not enough to gain confidence that we answered the original question. Since there is an infinite number of natural numbers (1,2,3, …etc), we have to find a different way of establishing or refuting the statement without listing an infinite number of examples. The clue is in how we write even and odd numbers.

An even number is a number divisible by $2$. We can write an even number as the product of two numbers, $2$, and another natural number $k>0$ in the form of $n_1=2k$. This number is even, because it is divisible by $2$. An odd number is one that is not divisible by $2$, or one where if divided by $2$ would have a remainder of $1$. Thus, we can express an odd number as $n_2=2m+1$, where $m>0$ is a natural number greater than zero.

Now we can see what happens when we add two even numbers, two odd numbers, and a mixture of numbers. Let’s add two even numbers first $n_1=2k$ and $n_2=2m$. The sum is $n_1+n_2=2k+2m=2(k+m)$ which is an even number.

How about adding two odd numbers $n_1=2k+1$ and $n_2=2m+1$? The sum is $n_1+n_2=2k+1+2m+1=2(k+m)+2=2(k+m+1)$ which is an even number.

Finally, how about adding mixed numbers one even $n_1=2k$, and one odd $n_2=2m+1$. Their sum is $n_1+n_2=2k+2m+1=2(k+m)+1$ which is an odd number.

By working through this simple math, we have gained insight into something drilled into us long time ago. Indeed, kids ask the smartest questions; don’t dismiss them, but use them to learn something new, or understand something you already know better.

Thursday, March 1, 2018

The Bystander Effect

At work, each floor has a kitchen area, with two beverage fridges, containing sodas, milk, and a variety of juices. Beverages are stocked weekly, and often checked for expiry or spoil. Last week, one of the fridges broke down, and to protect the milk from spoiling, someone moved it to the neighboring fridge. The next day I passed by the kitchen, the fridge was still broken, and more beverages started migrating to the working fridge. A week passed, and nothing changed. I realized that we are witnessing the bystander effect in action.

The bystander effect or bystander apathy is a phenomenon where people are less likely to act when others are present, because they assume that in a group someone eventually will. The apathy increases with the number of people in a group. The internet has a lot of examples of the bystander effect, and advice on how to circumvent it when you need to ask for help. Most of the examples involve dire and emergency situations, which highlight the incongruity of the help offered by the group. Interestingly however, we also experience the bystander apathy in milder non-emergency situations, for example when something is obviously broken, and we implicitly assume that someone else in the group will step up and fix it.

The solution to the fridge problem was very easy. I submitted a facilities request, and within an hour the fridge was fixed, and the beverages happily migrated to their respective locations. Perhaps the bystander apathy has its merit; someone eventually will act.

Wednesday, February 7, 2018

A computer in your hand

Not so long ago, my laptop was my preferred device to use after hours. Relaxing on the couch, I can check my work email, catchup on the news, read research papers, or enjoy reading books. As technology advanced, I could also stream videos and shows at my leisure without commercial interruptions, that for the last 10 years or so, I had no need for a cable subscription or a TV.
Then came tablets. I was not one of the early adopters, since laptops were sufficiently advanced at the time: they were faster, had a keyboard and a better screen resolution, and the short battery life was not a deterrent. An electric outlet was always close by, and I could still work while the laptop is charging.

Then came kids, and the chaos associated with them. Kids have a natural talent where they know exactly when you need to focus on something that’s not them or when you’ve been sitting down for longer than a minute, and they are compelled to rectify such injustice. This leads to a lot of work interruptions, lots of standing up and sitting down, putting the laptop aside, sometimes locking or unlocking the screen, and closing or opening the laptop lid with the eventual sleep and hibernation.  At the time, laptops had longer wakeup cycles, and you could not get back to what you were doing without waiting for a couple of minutes till the laptop became operable again. At this point, the laptop started becoming less convenient, and it was time to shift to the tablet world.

 Tablets are great consumption devices; you can read easily on them especially with their now larger screens, or you can watch movies, and consume other media. They started with terrible support for producing content: it was difficult to type an email, a document, or even a short sentence on the smaller touchscreen keyboard. With all the error correction, they were much slower than using a real keyboard, and not as convenient.

Then technology advanced again, and dictation and speech recognition became better. Also tablets became smaller, and phone became bigger and more performant, with large amounts of storage. Sometimes ridiculous storage, as my current smartphone has 256GB of space, comparable to my top of the line laptops of yesteryear. As a result, most of my afterhours consumption and production is done on my trusty smartphone, with dictation taking place of typing. The convenience of holding the phone with one hand and attending to the kids demands with the other is hard to describe. Moreover, setting the phone aside to use both hands, and then picking it up again and unlocking the screen to get back to the task at hand is almost instantaneous. Now everyone is happy because of mobility and convenience.

The vision of a computer at your fingertips is not new, but is starting to materialize now, and I can’t wait to see what the future holds with either virtual or augmented reality. Perhaps one day as Ray Kurzweil predicted in his book “the singularity is near”, we won’t have to hold phones or tablets, but instead have nanobots inside our bodies manipulating our neuron connections, and helping augment what we see and feel without using any external screens. A bit futuristic and farfetched perhaps, but sure could beat donning a heavy headset over one’s head. The computer at your fingertips will change to a computer in your neurons, or literally a computer in your fingertips.

Monday, September 11, 2017


Lunches at work are usually nothing to write about, however every now and then, we get an external restaurant that makes a memorable dish. A couple of weeks ago, that was the Cajun shrimp po’boy. The sandwich was relatively simple: a toasted baguette, a big of mayonnaise, some shredded lettuce, and seasoned Cajun shrimp, however the taste was amazing. I had an inkling about the origin of the name po’boy, but the price of the sandwich betrayed that thinking. A bit of research on the web revealed a couple of origin stories. The most plausible and heartwarming was on Wikipedia: that during a 1929 street car workers’ strike, restaurant owners served the sandwich to their striking colleagues for free, jokingly referring to the strikers as poor boys, after which the sandwiches took the name, and in the Louisiana dialect shortened to po’boy.

Thursday, September 7, 2017

Amazon Bookstores

In an era where most retailers are trying to decrease their physical presence, Amazon is doing the opposite  by opening physical bookstores across the US. I visited one last weekend, and was very impressed with the genius of using the store to promote Amazon services and devices.

First, unlike most bookstores that carry books on nearly every subject in the Dewey decimal system, the Amazon store carries a much smaller collection of books that are bestselling amongst customers in the geographical area. There were best sellers in fiction, art, cooking, business, self-improvement, health, children’s books, popular science, and that’s it. The pricing model was genius: if you have a prime membership you get the Amazon discounted price, and if you don’t you pay the book’s list price. My guess is that this will drive prime memberships as store patrons will opt to become prime members to nab the books they like at a discount.

Second, the store has prominent displays of the Kindle, Fire, and Echo devices, with helpful staff that answers any questions you have. Having the devices on display, and allowing customers to hold them and learn how they feel in their hands is very powerful. I was tempted to get a Kindle device despite my love of the Kindle App on my phone and tablet, and a Fire HD for the kids in addition to their iPads.

Third, despite the store being much smaller than typical bookstores, it felt warm and inviting. The store even had some comfortable chairs and couches for people to sit down, and enjoy a book or two.

It would be interesting to see how these bookstores fare when other stores failed. Apple, Microsoft, and now Amazon are proving that properly designed store can work, allowing people to touch and feel the products they are thinking of buying ahead of making a decision.

Friday, April 14, 2017

A paper a day keeps the dr away: FaRM -- Fast Remote Memory

Distributed systems have allowed applications to use more computation power, memory, and physical storage than is available on a single machine, enabling applications to tackle more complex problems. The capacity increase however comes at a cost: accessing remote resources is slower than accessing ones that are local to the machine. The paper “FaRM:Fast Remote Memory” tries to address the cost of accessing remote memory, and ways to make it faster.
The authors start by acknowledging that the major cost of accessing remote memory is the networking cost between machines through the TCP/IP stack, and that faster networks could do so much. They cite the case of MemC3—a state of the art key-value store—which performed 7x worse in a client-server setup than in a single machine setup, despite request batching. The authors ask the question if the TCP/IP stack overhead is that high, what if you bypass the complex protocol stacks, and use RDMA—remote direct memory access—to access memory on another machine? How would the performance look? The rest of the paper explores that question, and introduces FaRM: fast remote access memory.
The authors start with some background on RDMA. In RDMA, requests are sent between nodes over queue-pairs, and network failures are exposed as terminated connections. The requests go directly to the NIC, without involving the kernel, and are serviced by the remote NIC without the involvement of the CPU. Similar to DMA—direct memory access—a memory region is registered with the NIC before use, and the NIC driver pins the memory regions in physical memory, and stores virtual to physical page mappings in a page table in the NIC. When an RDMA request is received, the NIC gets the page table for the target, and uses DMA to access the memory.  Since NICs have limited memory for page tables, the tables are stored in system memory, and the NIC memory acts a cache. RDMA connects to remote machines typically over InfiniBand, but recently RoCE—RDMA over converged Ethernet—is becoming more attractive, with flow control, congestion notification, and a much cheaper price--$10/Gbps for 40 Gbps RoCE compared to $60/Gpbs for 10 Gbps Ethernet.
FaRM uses a circular buffer to implement a uni-directional channel. The buffer is stored on the receiver, and there is one buffer for each sender/receiver pair. The sender uses RDMA to write messages to the buffer tail, and advances the tail pointer on every send. It also maintains a local copy of the head pointer to prevent writing messages past the head. The receiver updates the head in the sender’s copy using RDMA as well, to create space in the circular buffer. The receiver polls for new items at the head of the buffer, and process them creating space as needed. The authors indicate that the polling overhead is negligible with 78 machines. They found that at that scale, the RDMA writes and polling significantly outperform the complex InfiniBand send and receive verbs. The authors ran a micro-benchmark to compare the performance of FaRM communication with TCP/IP on a cluster of 20 machines connected by a 40 Gbps RoCE network. The results show that FaRM’s RDMA based messaging achieves an 9x-11x higher request rate than TCP/IP for request sizes between 16 and 512 bytes. Another latency micro-benchmark showed that TCP/IP latency at peak request rate is 145x higher than that of RDMA based messaging for all request sizes.
To achieve that high performance, the authors had to do some optimizations. The first was using larger pages to reduce the number of entries in the NIC page tables by implementing a kernel driver for Windows and Linux that allocates large number of physically contiguous and aligned 2GB memory regions at boot time.
The authors also optimized the number of queue-pair data, by reusing a single connection between a thread and each remote machine, and sharing queue-pairs among many threads in a machine.
The authors introduce the FaRM API, which provides an event based programming model, with operations that require polling to complete a task taking a continuation argument—continuation function, and context pointer. The continuation function is called when the operation is done, and is passed the result of the operation and the context pointer. FaRM API also provides convenience functions to allocate and free objects, and support lock-free operations.
The authors use the APIs to implement a distributed hashtable, and a graph store similar to Facebook’s Tao, and evaluate the performance of both.
The experiments used an isolated cluster with 20 machines, with 40Gbps RoCE NIC. The machines ran Windows Server 2012RC, on 2.4GHz Xeon CPUs with 8 cores and two hyper-threads per core, and a total of 128GB of DRAM, and 240GB SSDs.
For the key-value store experiments, the authors used 120 million key-value pairs per machine, and configured the hash stores for 90% occupancy, and measured the performance for 1 min after a 20 second warm-up. The results show that FaRM achieves 146 million lookups per second with a latency of 35 microseconds. The throughput is an order of magnitude higher than MemC3, and the latency two orders of magnitude lower.
For the graph store, the authors implemented a store similar to Tao, and used Facebook’s LinkBench with its default parameters for degree and data size distributions, with a resulting graph with 1 billion nodes and 4.35 billion edges. On the 20 machine clusters, the authors got 126 million operations per second, with a per machine throughput of 6.3 million operations per second that is 10x that reported for Tao. The average latency at peak was 41 microseconds, which is 40-50x lower than the reported Tao latencies.
The authors end by describing some of the systems and libraries that use RDMA to improve performance.

Friday, March 24, 2017

Virtual machine could not be started because the hypervisor is not running

I wanted to experiment with TensorFlow, and decided to do that in a Linux VM, despite the fact that Windows Subsystem for Linux exists. In the past I used Sun’s, and then Oracle’s VirtualBox to manage virtual machines, but since my Windows install had Hyper-V, I decided to use that instead. The virtual machine configuration was easy, with disk, networking, and memory configurations non-eventful. However when I tried to start the virtual machine to setup Ubuntu from an ISO, I was greeted with the following error:

“Virtual machine could not be started because the hypervisor is not running”

A quick Internet search revealed that a lot of people have faced that problem, and most of the community board solutions did not make any sense. The hidden gem is this technet article, which included detailed steps to find if the Windows Hypervisor was running or not, and the error message if it failed to launch. In my case, the error was:

“Hyper-V launch failed; Either VMX not present or not enabled in BIOS."

The fix here is easy, and buried in another technet article. Simply reboot the machine entering BIOS setup mode, and disable VT-d and trusted execution settings. After a quick reboot, the hypervisor is happily humming along, and the setup of my Ubuntu VM is complete.