Concurrent Programming in High-Level Synthesis

This week, my student Nadesh Ramanathan presents our FPGA 2017 paper “Hardware Synthesis of Weakly Consistent C Concurrency”, a piece of work jointly done with John Wickerson and Shane Fleming.

High-Level Synthesis, the automatic mapping of programs – typically C programs – into hardware, has had a lot of recent success. The basic idea is straightforward to understand, but difficult to do: automatically convert a vanilla C program into hardware, extracting parallelism, making memory decisions, etc., as you go. As these tools gain industry adoption, people will begin using them not only for code originally specified as sequential C, but for code specified as concurrent C.

There are a few tricky issues to deal with when mapping concurrent C programs into hardware. One approach, which seems modular and therefore scalable, has been adopted by LegUp: schedule threads independently and then build a multithreaded piece of hardware out of multiple hardware threads. This all works fine, indeed there is an existing pthreads library for LegUp. The challenge comes when there’s complex interactions between these threads. What if they talk to each other? Do we need to use locks to ensure synchronisation?

In the software world, this problem has been well studied. The approach proposed by Lamport was to provide the programmer with a view of memory known as “sequentially consistent” (SC). This is basically the intuitive way you would expect programs to execute. Consider the two threads below, one on the left and one on the right, each synthesised by an HLS tool. The shared variables x and y are both initialised to zero. The assertion is not an unreasonable expectation from a programmer: if r0 = 0, it follows that Line 2.3 has been executed (as otherwise r0 = -1). We can therefore conclude that Line 1.2 executed before Line 2.2. It’s reasonable for the programmer to assume, therefore that Line 1.1 also executed before Line 2.3, but then x = 1 when it is read on Line 2.3, not zero! Within a single thread, dependence analysis implemented as standard in high-level synthesis would be enough to ensure consistency with the sequential order of the original code, by enforcing appropriate dependences. But not so in the multi-threaded case! Indeed, putting this code into an HLS tool does indeed result in cases where the assertion fails.

mp-fix1

My PhD student’s paper shows that we can fix this issue neatly and simply within the modular framework of scheduling threads independently, by judicious additional dependences before scheduling. He also shows that you can improve the performance considerably by supporting the modern (C11) standard for atomic memory operations, which come in a variety of flavours from full sequential consistency to the relaxed approach natively supported by LegUp pthreads already. In particular, he shows for the first time that on an example piece of code chaining circular buffers together that you can get essentially near-zero performance overhead by using the so-called acquire / release atomics defined in the C11 standard as part of a HLS flow, opening the door to efficient synthesis of lock-free concurrent algorithms on FPGAs.

As FPGAs come of age in computing, it’s important to be able to synthesise a broad range range of software, including those making use of standard concurrent programming idioms. We hope this paper is a step in that direction.

National Funding Formula

This post contains my personal response to the DfE’s second round consultation on the national funding formula for schools. Individuals, organisations, schools, etc., should feel free to reuse my response. My response is based on my earlier – and lengthier – analysis of the DfE’s proposals, which goes into much more depth. Those interested beyond the specific questions being asked by the DfE should consult the earlier post too.

Please note that consultation responses need to be submitted by 22nd March 2017 and can be done online. Please submit a response, even a partial one. This issue is too important to be ignored!

Q1. In designing our national funding formula, we have taken careful steps to balance the principles of fairness and stability. Do you think we have struck the right balance?

No.

The introduction of a funding floor is a fundamentally unfair approach. The stated purpose of the national funding formula was to provide fairness and end the “postcode lottery”. A funding floor, as envisaged by the consultation document, entrenches the postcode lottery in the current funding environment rather than eliminating it.

Q2. Do you support our proposal to set the primary to secondary ratio in line with the current national average?

Yes.

In the absence of further evidence, this seems like a sensible approach. However I am disappointed that further evidence has not been sought, e.g. a study of the relative primary/secondary performance across different local authorities with different ratios in place. By introducing the NFF, such studies will no longer be possible and so the Government is missing an opportunity to base these decisions on hard evidence.

Q3. Do you support our proposal to maximise pupil-led funding?

No – you should increase school-led funding compared to the current national average

This approach fundamentally ignores the different shape and makeup of schools. It would only be a reasonable approach if costs were all equally pupil-led. Instead, I support the principle of equalising disposable income per pupil. Once fixed costs are taken into account, this principle is opposed to that of maximising pupil-led funding.

Q4. Within the total pupil-led funding, do you support our proposal to increase the proportion allocated to the additional needs factors?

No – allocate a lower proportion to additional needs.

I would have said “don’t know” if given an option here, because the DfE has not presented any evidence that increasing this proportion is an appropriate decision. Equally, I do not have evidence that reducing it would be a good decision. Given local authorities central role in understanding local educational additional needs, in the absence of additional evidence, I believe LA averages should be used, which corresponds to a lower proportion compared to the proposals.

Q5. Do you agree with the proposed weightings for each of the additional needs factors?

Q5a. Deprivation – Pupil Based

No – allocate a higher proportion.

A number of studies, e.g. [1], have shown a stronger link between pupil-based deprivation indices and educational disadvantage than between area-based deprivation indices and educational disadvantage. Once again, a boundary discontinuity study would have been helpful, and I am disappointed that this work has not been undertaken.

[1] C. Crawford and E. Greaves, “A comparison of commonly used socio-economic indicators: their relationship to educational disadvantage and relevance to Teach First,” IFS Report R79, 2013.

Q5b. Deprivation – Area Based

No – allocate a lower proportion

See answer to “Deprivation – Pupil based”

Q5c. Low Prior Attainment

No – Allocate a lower proportion

There is simply no justification given in the consultation document for nearly doubling the funding going through this factor. It is frankly shocking that such radical changes can be proposed with no evidence presented in their favour.

No matter what proportion is decided upon for the initial implementation of the NFF, the Government should commit that in the future, should prior attainment metrics rise nationally, any funding lost to schools through the low prior attainment factor should be recycled into the APWU factor.

Q5d. English as an Additional Language

No – allocate a lower proportion

LAs have chosen to allocate an average of 0.9%. The proposal is to increase this to 1.2%. No evidence is presented to support this change, therefore I cannot support it.

On a related matter, for a fixed pot of EAL funding, there is an argument to be had over whether children would benefit more from considerable funding in year 1 for intensive English tuition to allow them to access the curriculum, rather than more “smeared out” three year funding at a lower level per year. Once again, it would be useful to see the research that suggests that one or the other approach actually reaps the greatest benefit before mandating EAL3.

Q6. Do you have any suggestions about potential indicators and data sources we could use to allocate mobility funding in 2019-20 and beyond?

None

Q7. Do you agree with the proposed lump sum amount of £110,000 for all schools?

7a. Primary

No – Allocate a higher amount

In order to ensure the principle of equal disposable income per pupil, the purpose of the lump sum should not be to “contribute to the costs that do not vary with pupil numbers” but rather to “be a genuine reflection of the costs that do not vary with pupil numbers”

7b. Secondary

No – Allocate a higher amount

See answer to “Primary”

Q8. Do you agree with the proposed amounts for sparsity funding of up to £25,000 for primary and up to £65,000 for secondary, middle and all-through schools?

Q8a. Primary

No – Allocate a lower amount

With a properly funded lump sum that reflects the costs that do not vary with pupil numbers, there is no need for a sparsity factor. Need for a sparsity factor is an admission that there are pupils in “non sparse” areas who are being deprived of appropriate disposable funding.

Q8b. Secondary

No – Allocate a lower amount

See answer to Primary

Q9. Do you agree that lagged pupil growth data would provide an effective basis for the growth factor in the longer term?

No comment

Q10. Do you agree with the principle of a funding floor?

The introduction of a funding floor completely eliminates the stated purpose of the NFF. It reintroduces and – worse – codifies – a postcode lottery based on historical funding rates.

Q11. Do you support our proposal to set the funding floor at minus 3%?

I do not support the funding floor.

Q12. Do you agree that for new or growing schools (i.e. schools that are still filling up and do not have pupils in all year groups yet) the funding floor should be applied to the per-pupil funding they would have received if they were at full capacity?

I do not support the funding floor

Q13. Do you support our proposal to continue the minimum funding guarantee at minus 1.5%?

No – the minimum funding guarantee should be higher (i.e. restrict losses to less than 1.5% per pupil in any year)

I strongly support the existence of a MFG as a way of phasing in funding changes. However, in the present financial climate a MFG of -1.5% is problematic coming on top of other issues such as the radical reduction in the education services grant to local authorities and the apprenticeship levy.

Q14. Are there further considerations we should be taking into account about the proposed schools national funding formula?

As a general principle, deviations from a move to average values across LA funding formulae should be justified and evidence-based. I have provided a lot more questions for consideration in a blog post at https://constantinides.net/2016/12/16/national-funding-formula-for-schools-a-critique/

Q15. Do you agree that we should allocate 10% of funding through a deprivation factor in the central school services block?

No Answer

I am disappointed the options in this questionnaire do not allow me to state “not sure”, because – once again – no evidence has been provided to justify the figure of 10%. What I can say confidently is that the overall level of central school services block is far too low. In effect schools are seeing a significant cut to their funding because they will need to fund services previously provided through the Education Services Grant.

Q16. Do you support our proposal to limit reductions on local authorities’ central school services block funding to 2.5% per pupil in 2018-19 and in 2019-20?

No – limit reductions to less that 2.5% per pupil per year

In line with my school-level comments on MFG, it is important to have transitional arrangements in place. Given the radical cut to the Education Services Grant, it is not clear why the proposed limit of 2.5% is so much greater than the school MFG rate of -1.5%.

Q17. Are there further considerations we should be taking into account about the proposed central school services block formula?

No Answer

Algebra and symmetry for 5-7 year-olds

At the encouragement of one of the teachers, I have resumed the math circle I was running a few years ago, jointly with her. Previous posts can be found here. This time we are targeting some of the youngest primary school children. So far, I’ve attended two sessions. In the first, we played with Polydron and I mainly used the session to observe the children and see what they’re capable of. In the second – described here – we experimented with symmetry.

Before the session, we created a few cardboard templates of three well-defined shapes, numbered 1, 2, and 3 in the picture below.

IMG_9197 (1).jpg

We told the children that we would be exploring a way of describing shapes as codes, and first had them cut out several copies of the shapes from coloured paper. This was not as easy as I had hoped – the children varied considerably in speed and accuracy of cutting.

We then told them that there were two operations that could be written down in our code, “next to”, written “;” meaning “the thing on the left of the semicolon is placed immediately to the left of the thing on the right” and “F” meaning “flip the shape in a vertical axis”. They seemed to understand this quite easily, and had no problems coming up and seeking clarification of any points. I hadn’t considered that they had not encountered the semicolon before, though, but this was not a problem, even if it was rendered more like a “j” in most of their written formulae.

We asked them to construct a couple of shapes, such as 2;F2 and F1;2, and then experiment with their own. They seemed to have a lot of fun, and the lower part of the photograph shows some that they were keen to show us when we reconvened in a circle on the carpet.

The children noticed that some shapes such as 2;F2 and F2;2 were symmetric, whereas some were not. I pointed out that nobody had tried to construct a shape such as FF1, and asked what that might look like. Several children correctly identified that FF1 would be indistinguishable from 1, so I wrote “FF1 = 1”, and I think I saw a flicker of an “ah ha!” moment in at least one child who seemed excited by the use of equations here.

At this point we ran out of time in our 1hr session. I would like to take this simple algebra further. In particular, I would like to get them to explore:

the generalisation from the observed FF1 = 1 to $\forallx.FFx=x.$
the observation that symmetry in a vertical mirror line corresponds to the statement Fx = x
the observation that all shapes of the form x;Fx are symmetric, and relate this to the algebraic definition of symmetry
the property F(x;y) = Fy;Fx

For those of a mathematical bent, these are the properties of a semigroup with involution.

I enjoyed myself, and I think the children did too!