Dev

Now to the meat of the problem, how the tasks actually run. Some of these tasks are going to run in parallel and that could cause threading issues. Looking at the original challenge there is an obvious sticking point. The two tasks ‘Preheat heater’ and ‘Mix reagent’ need to notify ‘Heat Sample’ they are done in a thread safe way so I will need a mutex. Alternatively I could use a thread safe boost::signal to inform the node that a task has finished, but that’s a bit heavyweight.

Another way though is if the computer is maintaining the state of each node, and the DAG is guaranteed not to change, then each node just needs to know how many inputs it has and keep a counter tracking how many have fulfilled their completion. std::atomic is designed for cases like this.

Because tasks can run in parallel, there may be more than one ‘cursor’ at the point of execution, so the  computer has to store a vector of cursors. Ideally the code will not continually start and stop threads to avoid a drain on resources, so future version will use a thread pool.

I can’t believe I’m posting these scrappy doodles but I’m chucking these pages out fast so I can crack on with code. This is this morning whilst waiting at the GP!

Day 2 sketch

Despite my expirations in optimising the DAG, I’m going to start with a simple version using std::function calls. I will fire off the threads using async which means I can take advantage of futures.

Futures will be particularly useful for updating my simulated hardware device with the output from the task. I know what inputs and outputs I am affecting in each task, so the future can return a block of ‘things to update’ on the hardware when the task has completed. Given my tasks specify what their inputs and outputs are I can validate that parallel threads are not going to access the same inputs and outputs and avoid collisions when the data is written. Due to the validation system, those collisions can be reported at builder time so you are guaranteed a clear flow.

For now I think the validation may be done through a function per tasks called ‘affects’ which returns which parts of the DeviceIO will be affected. For now this could just be a bit mask of input/output/cell IDs in an enum that are available on the device.

Whilst I’m here here’s last night’s godbolt doodle. I discovered that std::function does a lot more than a simple lambda. The compiler knows how to optimise lambdas. In this example I do everything with native function pointers for a ridiculously tight system https://godbolt.org/g/RTdnU1. This is more of a vanity project than something I will use for now because it would put significant constraints on the design before I’ve had a chance to shape it. Still it’s good to see what sort of methods I could use to optimise in the long run.

 

 


These are some embarrassingly loose sketches made en route to a friend’s leaving do. I wanted to cement my ideas about the builder class and these led into the idea of how one defines a hardware device. I was getting painfully close to template magic with these ideas but wanted to get an idea for the most expressive DSL for a recipe.

Day 1 eve A

I also sketched out some ideas for how to organise the project. And this also raised the question of whether I could statically compile the builders and take advantage of compiler optimisations so the DAG would have a very small footprint.

the ‘struct VolTRAX_0_0_1 is significant. Here I’m thinking of ways of declaring a device and how the state of that device is handled. Also if the device were a template class then you would have a very pluggable way of constructing recipes for multiple targets: you can reuse the core tasks but swap out different hardware. TBC

Day 1 eve B

Other notes that came up:

  • Should the DAG nodes be old school and use pointers or reference_wrappers to other nodes?
  • Don’t get too carried away with std::array in first pass. Write in std::vector, get unit tests working, then try to get static array version building as future goal.
  • How to implement current execution point ‘cursor’ and how is the running of each node handled. Should the computation trawl through the nodes or should there be an external ‘computer’ that maintains the cursors.
  • How do tasks signal they are finished, just notify by updating a counter, or do something snazzy with boost::signals2?
  • Quick todo list on setting up the GitHub repo!

After getting home I did a little late night exploration in terms of what one could do with static DAGs, e.g. std::array. This was off-piste but fun. Also I was using C++14 for some cases which, so I need to reign that in for the C++11 requirement spec for this challenge:

 

 


I sketched out a few early ideas in code to get a feel on good approaches in software. As the DAG is being generated by a builder, I wanted to see if it was possible to use std::array for inputs rather than std::vector. Regardless, my first doodle was more just a simple DAG structure exploring the concepts of adding hardware dependencies: https://godbolt.org/g/5y3Gsa

This was very useful in identifying a minimal DAG node, called a Task in this example. A few points:

  • Technically I don’t need to store the inputs as I’ll be processing this DAG top to bottom.
  • The idea of serial and parallel operations being simple derivatives of task
  • All operations on the device would be task derivatives.
  • Avoid cycles during insertion (possible to static assert if DAG size is known at constrcution?)

The main() block makes a conceptual jump into a nice syntax for a builder class that builds up the DAG in a readable way, sort of like a DSL for lab protocols. The base TaskBuilder class is responsible for generating a single DAG node. The TaskBuilderContainer is responsible for a list of DAG nodes, and is derived from Task with an extra method end() to indicate the end of a scope block.

These builder classes are nicely wrapped up readable class methods like add_ingredient() or preheat(). recipe() should really be called workflow() and takes a name.

 

 

 



									

A few days ago Nanopore sent me a technical challenge as part of their interview process. I’ve set up a a GitHub repo to track development progress. These are some notes before I go headlong into coding:

Day 1 – tech challenge received

The challenge involves building a DAG for a workflow. The first thing I did on receiving it was sketch out their example DAG to get a better feel for the behaviour of each node:

Day 1 sketch

Forgive the quality of these scans, I’m cobbling this together fast! The first sketch highlighted the scope of the design for the DAG:

  • Whether a task is manual or automatic.
  • Functional behaviour (e.g. display message, move sample).
  • Specification of ‘ports’ on device
    • Input where user adds sample. I’ll call these input_a, input_b etc.
    • Output where user removes sample. I’ll call these output_a, output_b etc.
    • General input/output ‘cells’ which is where the device is moving samples around, which I’m assuming to be a 2×2 grid from seeing the VolTRAX videos. I’ll call these cell_1_1, cell_2_4 etc.
    • Certain cells do work, e.g. heating, applying magnetic field. I’ll treat these like regular cells but give them special IDs like heater_1.

Example tasks and data required:

  • Add ingredient (manual): show message; input port ID; destination cell to move sample to.
  • Mix ingredients (auto): two registers to mix; cell where the sample ends up.
  • Preheat (auto): heater temperature; heater ID if there is more than one.
  • Heat sample (auto): input cell location; time on heater; header ID if there is more than one; output cell location.
  • Extract sample (manual): show message; output port ID.

This highlights some missing data in the DAG, that the operations of moving between certain cells should perhaps be nodes in themselves. For example the ‘heat sample’ task would be simpler if it was split up using move tasks:

  • Move sample from cell_1_2 to heater_1.
  • Stay on (preheated) heater_1 for 2 seconds.
  • Move sample from heater_1 to cell_2_3.

A few other things came up in this sketch:

  • Being a DAG it needs to avoid cycles.
  • The ports/cells give me a conceptual device to work with.
  • Validation. If I know all the inputs and outputs then I can run a validation step to ensure that anything that uses a particular cell or input has had that cell or input set up; i.e. check hardware dependencies.
  • To run the program the nodes will need to be sorted topologically. Not necessary if nodes are inserted in-order.
  • My sketch at the bottom left is my thinking about organising parallel data tasks which let to builder concepts detailed in next post. I think I can get a nice DSL together.

Starting in Ruby

Recently I’ve been chipping away at Jamis Buck’s ‘Mazes for Programmers’. I’m loving it and highly recommend the book. The code examples are quick to write, intuitive and good to learn from. They are written in Ruby and quietly introduce good design practices.

Whilst I’m working through the book I’m uploading my work in progress to https://github.com/alexallmont/JamisMazes. It’s been a while since I’ve pushed anything to GitHub because I started working on some of the ‘try at home’ sections at the end of each chapter; as I was working through it I started restructuring the core libraries on a new branch. I’ve gone down the refactor rabbit hole.

Moving to C++

I’ve managed to distract myself further by making my own maze library in C++. At the time of writing the repo https://github.com/alexallmont/MazeCpp is a simple C++ library which links into a demo and unit tests. My goal here was to brush up on my C++14 and experiment with continuous build systems. Over the last few days though I’ve been irked by the clunky design on the first draft. There’s lots of aliasing early on, the code was already feeling flabby.

Playing with templates

Today I’ve been experimenting with a templatised version that compiles down to practically nothing. I wanted to exploit that these mazes are fixed size, so I can use std::array to store data rather than std::vector. This means a huge amount of work can be done at compile time. Today’s experiments are at https://godbolt.org/g/ko0WIz.

The main class Grid2D is declared as a template with fixed rows and columns. Having the rows and column sizes declared at compile time means that a lot of the API boils down to constexpr functions. Rather than have a separate ‘Cell2D’ class, each Grid2D declares a nested Cell class that is a lightweight wrapper for querying individual cells in the maze graph.

Screen Shot 2017-06-11 at 17.26.09

I was hoping that I could reduce each cell to be a single integer, it’s index in the grid (row * NUM_ROWS + column). Unfortunately reducing to an int was not possible because each cell has query methods that reference non-static methods in Grid2D, so they also need to store an instance pointer to their owning grid. The alternative to this aliasing would be to pass the grid to every Cell function call, but that breaks the encapsulation and does not read well in code. However when building optimised the pointers boil away.

I’d prefer to store each cells Grid2D by reference rather than pointer and I’m exploring options as to whether that’s possible with std::array. As far as I know one can only use std::array on simple data types, no fancy construction is allowed, so the Cell class is friendly with Grid2D which does all the initialisation.

Regardless the simple test case compiles down ridiculously small, just 4 ops!

Screen Shot 2017-06-11 at 17.23.56

Screen Shot 2017-06-11 at 17.26.50


I wired up the the Chains prototype to display a series of events which can be controlled from the SoftPots. It’s cobbled together with scruffy code but it’s encouraging to see something responding real-time.

dsc_0344

There are some glitches in the inputs where it can jump in certain cases – it’s like there’s noise on the pots. This could be due to it being mounted on cardboard as the flex picks up subtle pressure changes. It’s pretty sensitive, just massaging the pot with a fingertip has a noticeable effect.

The display was up and running pretty quickly with Adafruit GFX and SSD1306 libraries. I bought some displays a while back, I think this one is a cheap version on Amazon and there were some helpful tips in some of the comments. I thought I would need to change the I2C address but I there was no need – just install the libraries in the Arduino IDE and experiment with the Adafruit demos, nice!

Plan for tomorrow:

  • Hook up the buttons and the input ports
    • buttons just needs pull up resistors
    • clock/reset inputs need transistors
    • analogue inputs need protection op amps
  • Mock up a first pass interface to record input from CV and softpots
    • I’m not sure how best to data collect so I’ll run a through iterations on a local repo and see how it goes.
  • Experiment averaging the inputs on the pots to avoid glitches.
  • If there’s any time I’ll wire up the outputs though they’ll be limited to 8 bit PWM for now.

Today I mocked up a rig for a rhythm module I’ve been dreaming up for ages called ‘Chains’. The three vertical bars are SoftPot linear touch-sensitive potentiometers and the screen will give visual feedback on what’s going on internally.

dsc_0341

The five inputs on the left will handle clock, reset and two individual analogue inputs which can be recorded to each chain – I’ll need some kind of toggle switch here to select.  The fifth input is an idea I’m keen to play around with: quantisation and anti-quantisation. The idea is 0V will leave a recording as-is, +5v will pull an event to the nearest 16th or 32th note, but -5v will push it away by the same amount. I have no idea if this will work but it’s there to try as the whole idea is ways of making rhythm more organic.

There are space for a few more inputs as needed but I’m going to start simple. Most of the interaction is done through the buttons under the screen. I’m using big, clear buttons for actions rather than fiddling around with a rotary encoder as this needs to be fast and intuitive for live interaction. The buttons will handle things like record, clear, motif load/save. I also need something for motif length adjustment – maybe individual tempo too – and I’m sure there will be more idea so the sixth button is for experimentation or may end up being a dreaded ‘shift’ button so I can double up operations on the five other buttons.

Finally the outputs on the right simply dump out whatever is on a particular chain at that point in time, be it CV or gate info. I’m glad I built this on cardboard because it gave me a better sense of positioning the controls away from the pots, it’s fun developing UX physically (well, it’s not really UX if you’re a purist, but it’s a step up for me dreaming things up and expecting them to work first time!).

dsc_0342

From the back the board is a scramble. I’m using the bigger Arduino as a mock up purely because I don’t know how many inputs or outputs I’ll need for now, it’s overkill. The final version I’d like to bake into an AVR but I’m thinking that being able to upload firmware will be a massive boon for rapid development if I ever made this thing commercially.


I’ve been learning more C++ 11/14 and I initially wanted to build a nice API using variadic templates. When used correctly one can build a clean API with templates that compile down to very small code. Unfortunately AVRGCC does not yet support C++ 11/14 so I can’t follow that route.  Here’s my bullet point summary of the day’s findings:

  • Early template classes experiments messy/confusing.
  • C++0x14 does not work on AVR right now anyway.
  • Linked lists simply don’t optimise away.
  • Virtual methods don’t optimise away.
  • Best approach seems to be general class.
  • Static functions in a namespace compile even smaller than class.

My strategy here was to start with a nice OOP design and rapidly iterate ideas using Compiler Explorer to see where it took me.  I built with AVR gcc 4.5.3 with the flags -Winvalid-pch -Wall -Wno-long-long -pedantic -Os -ggdb -gstabs -mmcu=atmega328p -fdata-sections -ffunction-sections -fsigned-char

Test 1 : Linked lists

My starting point was a singly linked list of AdcInputs. The AdcManager polling the next via interrupt whilst traversing the list. The derived classes would present a nice API.

adcinput

Given my code sample I was hoping the compiler would be clever enough to optimise a lot away, but I am storing data in virtual classes so there’s a lot of vtable setup, calls and the pointers in the linked list are still used in code:

adcinputtest1

Tests 2 – (n-1) : No man’s land

Here’s where it gets a bit messy going through my notes because I didn’t keep copies of all of my in-progress code. In summary I realised that virtual classes and linked lists were not the way to go and experimented with template magic and functors before settling on a simple solution of a central do-it-all manager class.

The problem was making a reasonably friendly access interface out of it. For my applications there are only a few variations on the types of ADC interface, they mostly store a uint8_t as the value – with the edge case of using 10 bit resolution – so would it be possible to cram all the other data into another byte? I could use say 2 bits to store the type of interface and the remaining 6 could be used by each interface’s implementation. For example, storing a ‘pushed’ state for a SoftPot.  In total that gives me a standard 2 byte struct for each interface which I can simply store in an array for the manager.

The bit wrangling ideas came strongly from this hybrid data structures video. They use a heavily templatized method to access bits whilst remaining robust enough to avoid memory stamping.  I’d like to that more in future but for now I’m just using plain old bit fields.

Swapping out the linked lists for a fixed array adds memory overhead because that chunk of memory is always used. However I select AVR chips based on spec; if I only need 3 inputs then I look for the closest match chip rather than an overspecced AtMega328.

This code is an experiment during this stage.  It’s not pretty but I’m sharing it because it helped me realise the value of using static correctly in optimisation. Here’s what happens when you remove the static keyword from AdcRunner::update():

adcinputtest2

Test 3 : template accessors

With the manager ‘class’ now simply being a bunch of static functions, I’m using a templatized base class to give the user access to each one. Here’s the core class. ADC_TYPE is an enum that defines my fixed set of ADC interfaces. The interface stores a reference to data which is handled by the manager. The idea is as a client you use these objects on the stack merely as accessors to the manager’s data, and that the manager uses these objects to update its data correctly.

template <Type ADC_TYPE>
class AdcInput
{
public:
  AdcInput(Data& data) : m_data(data) { }
  static Type getType()        { return ADC_TYPE; }
  static uint8_t getTypeBits() { return (uint8_t)getType() & 0x03; }
protected:
  Data& m_data;
};

Here’s an example concrete implementation softpot input.  It has accessors for getting the value and determining if it is pressed.  The update method will be called from the manager, it’s a bit ugly but it’s in progress.

class Softpot : public AdcInput<kSoftPot>
{
public:
  Softpot(Data& data) : AdcInput(data) { }
  uint8_t getValue()   { return m_data.value; }
  bool isPressed()     { return (m_data.info & (1 << 4)) != 0; }
  void adcUpdate(); // TBC... this is how the manager updates this data
};

Here’s some code to get a feel for the API

  init_adc();
  add_adc<Pot>(0);
  add_adc<Softpot>(1);
  
  Pot p1 = get_adc<Pot>(0);
  Softpot p2 = get_adc<Softpot>(1);

  for (;;)
  {
    uint8_t val = 0;
    if (p2.isPressed())
      val = p1.getValue() + p2.getValue();
    else
      val = p1.getValue() - p2.getValue();
  }

 

adcinputtest3

The full version of the test code and compiled output is here and the generated output is on the right.

The current problem with this is that there is no fail-safe on getting the wrong type of object. For example in the above code I have a pot on 0 and a softpot on 1, but there is nothing stopping me trying to read 0 as a softpot. This is not the right place to use exception handling. One option is to store a block of clearly invalid data like 0xFFFF, which you can pick up in debug, but it irks me.

Next step is to try this in action on the AVR and look at the generated assembler with the interrupt handler in place. I have no doubt it will be a little bit longer than writing the code in plain C but I wanted to experiment with something more scalable, and I’ve learned a few things on the way hence this blog post.

Also learned today

  • Today I needed a nice UML editor so I turned to Stack Overflow for advice.  I initially tried Umler, then ArgoUML because I like the developers but it’s a real fiddle (no cut/paste/undo!) so I went Dia which immediately felt nice.  Also jogged my UML memory with this guide.
  • It’s hard to keep blog posts short. Bear with me on this, I’m learning the ropes!

softpotSeveral of my recent 8 bit microcontroller projects need multiple analogue inputs. I want a nice API that allows me to have different interfaces for getting analogue values, for example reading a straightforward pot as 0-255 or 0-1023, or a SoftPot membrane potentiometer where I may also want to track whether or not it’s
currently pressed.

adc_simple

Reading analogue inputs on AVR chips takes time and the lazy approach to reading an analogue value is to set up the registers to read a value and simply wait for it to come in.  You do something like this:

    ADMUX |= _BV(MUX0);
    ADMUX |= _BV(ADLAR);
    ADCSRA |= _BV(ADPS1) | _BV(ADPS0) | _BV(ADEN);
    while (ADCSRA & _BV(ADSC));	// !

That while loop is just eating cycles whilst we’re waiting for the ADC to return a result.

adc_interruptThe best way to avoid this wait is to set up the ADC to start reading a value and when it’s ready send an interrupt to get the result.

The interrupt can either use the value immediately or stash it away in a stored value so it can be picked up later on in the main loop.

This approach saves wasting cycles but still has a problem: the ADC can only read one value at a time and I need multiple inputs.

adc_roundrobin

The workaround for this is to make the interrupt run continually and constantly read each ADC value in turn.

The poll requests requests a value for a certain analogue input and when the ADC interrupt is fired off, it re-polls for the next one.  This runs perpetually whilst interrupts are enabled.

The interrupt can act on the values immediately or – if we’re not concerned about keeping everything perfectly in sync – the values can simply be stored in data so it can be picked up in the main thread.

In the next post I’ll explain how I iterated this round-robin in building a fast and clean API for AVR chips.


Since my PhD collapsed I’ve was out of action on the making front. I’ve taken some time to clear my head and now I’m getting the urge to create things again. It’s coming on strong and the problem is when this happens I get dozens of ideas at once, and then I start them all at once, so it all falls apart pretty quickly!

To get past this I’ve resolved to take the path of the the self-indulgent project dev blog. Whatever happens on dev days gets written, the good bits and the bad bits – and there are a lot of bad bits. I’m hoping that this will give me a healthier perspective on ‘failure’ days where I’m going in circles making an API that it turns out I didn’t need, or when I get one of those days where Windows/installers failing seems to waste a whole day *

So for starters, here’s what went well today. I drove up to Nottingham to get myself a signal generator I can gut to make a music interface.  Here’s whats I gots:

marconi-panel

It will anger radio hams that I’m gutting such a beautiful thing but it’s bought more as spares and I’d probably fry myself if I tried to wire it up to the mains. I’m aiming to make this into an exploratory audience-based music interface, largely focused on rhythm. This is exactly the sort of thing my PhD was focused on – dammit – but putting frustrations aside I’m going to just going to build what I can an see where it takes me.

The unit is a Marconi CT452A and it weighs 65lbs. The insides are incredible, I was expecting straightforward vernier potentiometers on the controls but it is heavily mechanical with springs, chains and gears.  I’ve not opened the main electronics section but there are a number of exposed valves and massively enlarged transformer, caps and bridge rectifier.  It’s an old selenium one from General Electric:

marconi-super-diode

So the first part of this project – the pick up – is done. Next I need to strip back the innards and see how easily I can interact with those controls.

What didn’t go so well today was I was planning to do a bit of sight-seeing in Nottingham, but I got there so late I missed the castle. I made it the famous pub ‘Ye Olde Trip To Jerusalem’ though and the contemporary arts gallery, which was typically pretentious, but in the foyer I found an awesome book on Kubrick by Tashen. Actually one good thing there was a dark corridor with sound in the walls, I’d love to have been in a bigger version of it:

dsc_0326

I drove today to ‘Black Box Thinking’ by Matthew Syed on audible, which is part of the motivation for me getting into writing this. It’s really good.  Another good thing was this morning I managed to squeeze one more desk into the workshop which is a hugs win as every other surface is covered in half-finished projects.

* Footnote: on failed APIs and Windows-waste days. I will blog a little about these later because despite being an annoyance it’s wrong to consider them a fail or waste; I learn a lot from these things, the problem is just I don’t write it down anywhere so I forget!  I’ll aim to post about the API experiments tomorrow, it’s an interface for reading Pots and SoftPots on AVRs.