Coherence When You Need It

This week, my PhD student Felix Winterstein presented our work (joint with Intel and MIT) on how to customise memory systems to support parallel applications, at the FPGA 2015 conference.

If you are working with FPGAs, you have a huge freedom to develop an arbitrary on-chip memory system to support your application. Tools are getting quite good at developing such systems for regular array based code. But pointer manipulating programs that build, operate on, and destroy memory structures on the fly will not pass through commercial HLS tools, let alone produce good quality results.

We’ve shown that this issue can be addressed using a tool we’ve developed based on the theoretical foundation of Separation Logic. The tool automatically figures out when functional units can have private on-chip caches, which functional units need shared coherent caches, and – in the latter case – when commands can be reordered to aid parallelisation. It uses this analysis to automatically produce C source code that will pass through commercial HLS tools, providing the necessary hints and pragmas to parallelise the code, and automatically generates the on chip caches to support the parallel datapath.

I’m really very excited about this work, I view it as a big step towards efficient automatic hardware implementation of full-featured C code.

Math Circle Session 5: Powers, Limits, and Fractals

Yesterday saw the next installment of our math circle with primary school children. Again, following but extending Rozhkovskaya’s book, we used fractals as an interesting way in to consolidate (and in the case of the younger pupils, introduce) powers of numbers, to explore the children’s intuition about infinite series, and to make some pretty pictures!

We started by producing a fractal tree. The rule is simple: after Year 1, the trunk has grown. At the end of Year 2, two branches have grown from that, after Year 3, two further branches from each existing branch, and so on. Children were quickly able to tell us that the number of branches doubled each year, some took great pleasure in calculating or reciting powers of two. The template for this exercise was taken from Rozhkovskaya’s book, and is quite clever: lines are drawn across the page heights of 8 squares, 12 squares, 14 squares, 15 squares, and 15.5 squares, and each successive year’s branches should be drawn to reach the corresponding height. A bird is drawn flying around 18 squares up. The question is posed: will the tree ever reach the bird?

The children had mixed views on whether the tree will reach the bird. The most common view was that it must. One of the older children was able to provide a line of reasoning: “Each time, the height of the tree increases. Since it is always increasing, even by small amounts, it must eventually reach any height.” We then looked at how much gap there is between the height of the tree and a line of height 16 as the years progress: 16 at the beginning, 8 at the end of Year 1, 4 at the end of Year 2, and so on. Children could see that there was always a positive gap between the height of the tree and the height 16, for any finite number of years. However, this clashed with several children’s intuition, and it took quite a lot of discussion before it was generally accepted that an infinite series can sum to a finite limit. One of the youngest children in the group asked some very probing questions, such as “is infinity a number”, which led to some useful side discussions. Random banter between children later in the session about “hacking” their siblings’ passwords led onto a consolidation of this discussion by asking the question “If you had to press an infinite number of keys on a keyboard, could you do it in a finite amount of time? No? What if the first key took 8 seconds to press, the next 4, the next 2, and so on…”

We then moved onto a practical activity of constructing a sequence of approximations to the Sierpinski triangle by sticking little white triangles on coloured paper (pictured). One of the children noticed quickly, and was able to clearly explain, that the number of white triangles was increasing in powers of three. At this point we ran out of time, and our session ended. I intend to pick up and use the Sierpinski triangle again soon in math circle, through Pascal’s triangle modulo 2.

Math Circle Session 4: Ciphers

Today saw the fourth session of our math circle. Attendance was down, and there was a sombre mood, due to a tragic event to hit the the school community today.

We went ahead with the three children who came, looking at ciphers. Following the guidance and resources in Rozhkovskaya’s book, we looked at the following activities:

We started with some plaintext words and one ciphertext word, and the kids very quickly spotted, without any help, which plaintext word corresponded to the ciphertext word, on the basis that both had a double letter in a certain place and they had the same number of symbols.
We showed how a coding wheel can be used to produce a Caesar shift cipher, and got them to actually build such a wheel.
We queried how many possible ciphers could be constructed with such a wheel. Interestingly, this was not obvious to the children at first, and a common answer was “infinite”. On questioning, this is because they were considering all integer shifts, i.e. mapping the letter $n$ to the letter $n+k$ for some key $k$ , and forgetting the modulo arithmetic in play, despite having the wheel in front of them.
We got them to produce coded messages to each other using the wheel, which they seemed to enjoy. Our initial plan was to have them pass the message and the key to the next child to decode. However, they immediately attempted to decode without they key by looking for patterns, so we didn’t stop this. One key pattern they spotted included the limited number of two letter words in English, allowing them to enumerate possible keys on two-letter words in the ciphertext. Another was the limited number of letters in the alphabet that can appear twice consecutively in an English word, again allowing for enumeration.

There’s a lot more that can be done with ciphers, and I expect we’ll continue this for another session.