Category: Computational Thinking

Getting off the beach, fast

by Paul Curzon, Queen Mary University of London

Paul goes on holiday and sees how a car park can work like a computer.

Fibre optic cables image by Chaitawat Pawapoowadon from Pixabay

Computers get faster and faster every year. How come? Because computer scientists and electronic engineers keep thinking up new tricks, completely new ways to make them go faster. One way has been to shrink the components so signals don’t have as far to go. Another is to use the same trick they were using in a beach car park I came across on holiday.

Woolacombe coast image by adammphillip5 from Pixabay

Woolacombe Sands in Devon is one of the most popular beaches around. There is a great expanse of beautiful sand as well as rocks for kids to climb on and good surfing too. The weather is even good there – well most of the time. The car park, right on the edge of the beach fills in the morning. Since most people arrive early and stay all day it’s a standard price of £5.50 for the day. Entry and exit barriers control the numbers. The entry barrier only allows a car to go in if there is a space and another allows people out when they have paid.

That’s where there is a problem though. The vast majority of people leave around 5pm as the ice cream vans pack up and it’s time to look for dinner. The machine only takes coins, and you insert the money from your car at the barrier. Each driver has to fumble with 5 one-pound coins and a 50p and that takes time. Once the current car moves on out there is then another delay as the driver behind pulls forward to get into a position to put their money in. Without some thought it would lead to long queues behind. Not only that it wouldn’t be very green. Cars are at there worst pumping out pollution when in a jam.

The last thing you want to do to a family who’ve had a great day on your beach is then irritate them by clogging them up in a traffic jam when they try to leave. So what do you do? How can you speed things up (and make sure you aren’t just moving the queue to the morning or to some other ticket machine somewhere else)?

The problem is similar to one in designing a computer chip. Think of the cars as data waiting to be processed (perhaps as part of a calculation) and the barrier as a processing unit where some manipulation of that data is needed. Data waiting to be processed has to be fetched before it can be used, just as the cars have to move up to the barrier before the driver can pay. The fact that the problems are so similar suggests that a solution to one may also be a a solution to the other.

Speed it up

There are lots of ways you could change the system to improve the speed of cars being processed in the car park. This speed that data passes through a system is called the ‘throughput’ of the system. Woolacombe have thought of a simple way to improve their throughput. They put a person with a bit of change next to the barrier to help the drivers. This allows them to keep the relatively simple barrier system they have. It also has advantages in keeping the money in one place and being a foolproof way of ensuring there is a space for everyone who enters. It still maintains all the safeguards of the ticket barrier though. How can that one person speed things up?

What would you do?

So what would YOU do if you were that person? Would you speed things up? Or would you just stand there powerless watching the misery of all those families?

Pound coins image by PublicDomainPictures from Pixabay

The first thing you could do is to stand by the machine and take the change off the driver and insert it yourself. That will speed things up a little bit because it takes longer for drivers to put the money in as they have to stretch out the window of a car. Also if the driver only has a five pound note you can take it and just insert coins from your change bag rather than wasting time passing it back to the driver to then insert. Similarly if the driver only has 50 pence pieces say, rather than wasting time inserting 10 of them you can take them and insert 5 one-pound coins.

You’ve done some good, and removed problems of the slow people inserting coins but you haven’t really solved the bad problems. Cars aren’t moving at all while you are inserting the 6 coins, and after each car moves through the barrier you are doing nothing but waiting for the next car to pull forward. In an ideal system, with the best throughput, the cars barely stop at all and you are constantly busy.

A Pipeline of Cars

It turns out you can do something about that. It’s called pipelining. There is a way you can be busy dealing with the next car even before it’s got to you. You just have to get ahead of yourself!

Cars image by Ambady Sasi from Pixabay

How? Before the first car arrives, insert 5 pound coins into the machine and wait. As the driver gets to you and gives you the money, insert his or her 50p, keeping the rest. The barrier opens immediately for the driver who barely has to stop. Better still you are now holding 5 pound coins that you can insert as the next car arrives, leaving you back in an identical situation. That means the next car can drive straight through too, and you are constantly busy as long as there are cars arriving.

Speedy data

So you’ve helped the families leaving the beach, but how might a similar trick speed up a computer? Well you can do a similar thing in the way you get a computer processor to execute the instructions from a program. Suppose your program requires the processor to get some numbers from storage, process them (perhaps multiplying the numbers together) and then store the result somewhere else for later use. Typically a program might do that over and over again, varying where the data comes from and how it is processed.

Early computers would do each instruction in turn – doing the fetching, processing and storing of one instruction before starting the next. But that is just like a car in our car park coming to the barrier, being processed and leaving before the next one moves. Can we pull off the same trick to speed things up? Well, yes of course.

All you need to do is overlap the separate parts. Just as at any time in the car park a car will be driving out, a second will be handing over money and a third pulling forward, the same can happen in the computer. As the first instruction’s result is being stored, the next instruction can already be being processed and the data from the one after that can be fetched from memory. Just by reorganising the way the work is done, we have roughly tripled the speed of our computer as now three things are happening at once.

What we have done is set up a ‘pipeline’ – with a series of instructions all flowing through it, being executed, at the same time. Woolacombe has a pipeline of cars, but in a computer we pipeline data. Either way things get done faster and people are happier.

Computer science happens in some unexpected places – even at the beach – but then perhaps that isn’t so surprising given computers are made of sand!

Toy truck on sand image by Sebastian Mey from Pixabay

This article was originally published on the CS4FN website.

Other beach-themed articles on this blog include how the origins of how Paul learned to program while on holiday (“The beach, the missionary and my origin myth”) and messages hidden (steganography) within the stripes of deckchairs (“Encrypted deckchairs”).

The beach, the missionary and my origin myth
Encrypted Deckchairs

EPSRC supports this blog through research grant EP/W033615/1.

Pit-stop heart surgery

by Paul Curzon, Queen Mary University of London

(Updated from the archive)

The Formula 1 car screams to a stop in the pit-lane. Seven seconds later, it has roared away again, back into the race. In those few seconds it has been refuelled and all four wheels changed. Formula 1 pit-stops are the ultimate in high-tech team work. Now the Ferrari pit stop team have helped improve the hospital care of children after open-heart surgery!

Image by Peter Fischer from Pixabay

Open-heart surgery is obviously a complicated business. It involves a big team of people working with a lot of technology to do a complicated operation. Both during and after the operation the patient is kept alive by computer: lots of computers, in fact. A ventilator is breathing for them, other computers are pumping drugs through their veins and yet more are monitoring them so the doctors know how their body is coping. Designing how this is done is not just about designing the machines and what they do. It is also about designing what the people do – how the system as a whole works is critical.

Pass it on

One of the critical times in open-heart surgery is actually after it is all over. The patient has to be moved from the operating theatre to the intensive care unit where a ‘handover’ happens. All the machines they were connected to have to be removed, moved with them or swapped for those in the intensive care unit. Not only that, a lot of information has to be passed from the operating team to the care team. The team taking over need to know the important details of what happened and especially any problems, if they are to give the best care possible.

A research team from the University of Oxford and Great Ormond Street Hospital in London wondered if hospital teams could learn anything from the way other critical teams work. This is an important part of computational thinking – the way computer scientists solve problems. Rather than starting from scratch, find a similar problem that has already been solved and adapt its solution for the new situation.

Rather than starting from scratch,
find a similar problem
that has already been solved

Just as the pit-stop team are under intense time pressure, the operating theatre team are under pressure to be back in the operating theatre for the next operation as soon as possible. In a handover from surgery there is lots of scope for small mistakes to be made that slow things down or cause problems that need to be fixed. In situations like this, it’s not just the technology that matters but the way everyone works together around it. The system as a whole needs to be well designed and pit stop teams are clearly in the lead.

Smooth moves

To find out more, the research team watched the Ferrari F1 team practice pit-stops as well as talking to the race director about how they worked. They then talked to operating theatre and intensive care unit teams to see how the ideas might work in a hospital handover. They came up with lots of changes to the way the hospital did the handover.

For example, in a pit-stop there is one person coordinating everything – the person with the ‘lollipop’ sign that reminds the driver to keep their brakes on. In the hospital handover there was no person with that job. In the new version the anaesthetist was given the overall job for coordinating the team. Once the handover was completed that responsibility was formally passed to the intensive care unit doctor. In Formula 1 each person has only one or two clear tasks to do. In the hospital people’s roles were less obvious. So each person was given a clear responsibility: the nurses were made responsible for issues with draining fluids from the patient, anaesthetist for ventilation issues, and so on. In Formula 1 checklists are used to avoid people missing steps. Nothing like that was used in the handover so a checklist was created, to be used by the team taking on the patient.

These and other changes led to what the researchers hoped would be a much improved way of doing handovers. But was it better?

Calm efficiency saves the day

To find out they studied 50 handovers – roughly half before the change was made and half after. That way they had a direct way of seeing the difference. They used a checklist of common problems noting both mistakes made and steps that proved unusually difficult. They also noted how well the teams worked together: whether they were calm and supported each other, planned what they did, whether equipment was available when needed, and so on.

They found that the changes led to clearly better handovers. Fewer errors were made both with the technology and in passing on information. Better still, while the best performance still happened when the teams worked well, the changes meant that teamwork problems became less critical. Pit-stops and open-heart surgery may be a world apart, with one being about getting every last millisecond of speed and the other about giving as good care as possible. But if you want to improve how well technology and people work together, you need to think about more than just the gadgets. It is worth looking for solutions anywhere: children can be helped to recover from heart surgery even by the high-octane glitz of Formula 1.

More on …

Magazines …

EPSRC supports this blog through research grant EP/W033615/1. 

Lego Computer Science: Logic with Truth Tables

by Paul Curzon, Queen Mary University of London

Lego of a truth table for NOT P
The truth table for NOT P. A yellow brick represents P. Blue means True and Red means false. Read along the rows to get the meaning of NOT P when P is true or false.

We have seen how to represent truth tables in lego. Truth tables are a way of giving precise meaning to logical operations like AND, OR and NOT. They are also give a way to do logical reasoning following a simple algorithm.

That’s Not Not True

You may have been pulled up in English and told you just said the opposite of what you meant, after saying something like “There ain’t no way I’m doing that”. This is a “double negative” as the “n’t” in “ain’t” is really “not” so followed by “no way” you are actually saying “not not way” or overall: “I am doing that”. Perhaps the most famous double negative is in the Rolling Stones song “(I can’t get no) satisfaction”. English is very flexible though and double negatives like this don’t cancel out but just become a different way of saying the negative version. In logic two negations do cancel out, though. Let’s take a purer version to work with: the statement “I am not not happy”. What does this mean? In logic the basic proposition here is “I am not happy”. The logical statement is “NOT (NOT (I am happy))”.

We can prove what this means using truth tables. We can do more than just prove what this single statement means. We can prove what all double negatives mean, more generally. We do this by replacing the proposition “I am happy” with a variable P. It now becomes NOT (NOT P) or in our lego version where we use a yellow brick to mean a proposition, P:

NOT NOT P

This is just syntax, just a sequence of symbols. It doesn’t give us any meaning on its own. We can build truth tables in Lego for that. We start from the variables that are at the inside of the logical expression which here is just the variable P. We list in a table column the possible values it can take (true or false).

This shows P (yellow) can be either be TRUE (blue) or FALSE (red). Now we build up the logical expression of interest a column at a time. NOT is applied to P, so we add a new column for NOT P and use the truth table for the operator, NOT, to tell us what lego brick to put in each row based on the lego brick already there. The NOT truth table is at the top of the page. It says if you have a blue brick in a row, place a red brick there. If you have a red brick, put a blue brick there. This gives us a new filled out column for (NOT P) which is just a copy of the NOT truth table (but bare with us that was just a simple case). We get:

Moving outwards in the expression NOT (NOT P)), we now look at the operator applied to (NOT P). It is NOT again. We add a new column to our truth table and again use the NOT truth table to work out the new values, but this time applied to the column before (the NOT P column). The NOT truth table says put a blue brick for a red brick, and a red brick for a blue brick in the column it is being applied to (the NOT P column). This gives:

NOT (NOT P) lego truth table

The result is a truth table with coloured bricks identical to that of the original column for P. Switching back from lego bricks to what the columns mean, we have shown that the NOT(NOT P) column is the same as the P column, or in other words that NOT(NOT P) EQUALS P (whatever value P has).

We can actually go a step further though, because equivalence is just a logical operation with its own truth table. It gives true if the two operands have the same value and false otherwise (or in lego terms if the bricks are the same colour the answer is a blue brick and if they are different colours the answer is a red brick. The truth table looks like this:

P EQULAS Q lego truth table

We can use this truth table to calculate whether two lego truth table columns are equal or not just by looking up the combinations in this EQUALS truth table. Continuing our example we can carrying building our truth table about NOT(NOT P)). To make things clearer first add a column corresponding to P again. That means we will be applying the EQUALS operator to the last two columns. As before, for each row, look up the corresponding pattern for those last two columns in the EQUALS truth table to get the answer for that row. In the first row we have two blue bricks so that becomes a blue brick according tot he EQUALS truth table. In the next row we have two red bricks. That also becomes a blue brick. This gives:

Lego truth table for NOT (NOT P) EQUALS P

The thing to notice here is that all the entries in the final answer column are blue lego pieces. Switching back from the lego world to the logic world, what does this mean? Blue is true so all rows in the answer are true. That means whatever value of the proposition P the answer to NOT (NOT P) EQUALS P is true. We have proved a theorem that this is always true. We have shown by building with lego that a double negation cancels itself out.

Logical expressions like this that are always true (whatever the values of the variables) are called tautologies. We can tell something is a tautology, so we have proved a theorem, just by the simple manual check that its truth table values are true (or in lego all blue).

The important thing to realise about this is all the reasoning can be done without knowing what the symbols mean, and certainly not worrying about English words, once you have the truth tables. You do it mechanically. You do not need to think about what, for example, red and blue mean until the end. At that point you return to the logical world to see what you have found out. All blue means it is always true! You can also at that point substitute back in actual words of interest into the statements proved. P means “I am happy”. We started by asking what “I am not not happy” means. We converted this to “NOT (NOT (I am happy))”. By swapping in “I am happy” for P in our theorem gives us that NOT (NOT “I am happy”) EQUALS “I am happy”, or that “I am not not happy.” just means the same as “I am happy”

We have been reasoning about English statements, but this kind of reasoning is the basis of all logical reasoning and essentially the basis of formal verification where the meaning of programs and hardware is checked to see if it meets a specification. It tells you what a test in a program like “if (! temperature != 0) …) means so does for example, or what a circuit with two NOT gates does.

And lego logic has even given us a way to prove things just by building with lego.

Lego Computer Science

Image shows a Lego minifigure character wearing an overall and hard hat looking at a circuit board, representing Lego Computing
Image by Michael Schwarzenberger from Pixabay

Part of a series featuring featuring pixel puzzles,
compression algorithms, number representation,
gray code, binary and computation.

Lego Computer Science

Part 1: Lego Computer Science: pixel picture

Part 2: Lego Computer Science: compression algorithms

Part 3: Lego Computer Science: representing numbers

Part 4: Lego Computer Science: representing numbers using position

Part 5: Lego Computer Science: Gray code

Part 6: Lego Computer Science: Binary

Part 7: Lego Computer Science: What is computation (simple cellular automata)?

Part 8: Lego Computer Science: Truth tables

Part 9: Lego Computer Science: Logic with truth tables

More on …

EPSRC supports this blog through research grant EP/W033615/1, The Lego Computer Science post was originally funded by UKRI, through grant EP/K040251/2 held by Professor Ursula Martin, and forms part of a broader project on the development and impact of computing.