Freesteel Blog » 2006 » October

Wednesday, October 25th, 2006 at 8:37 am - - Whipping 2 Comments »

I got my FOI request answered and obtained the 132 page framework contract that was signed between Becta and 16 companies who are to supply ICT equipment to schools.

The purpose of this agreement is to make the procurement of this off-the-shelf computer equipment for schools from an official cartel of 16 companies legal under European competition law. They were chosen (the contract appears to say) because they were least likely to go insolvent and be unable to provide support services for this standard gear — which of course is unlikely with this guarenteed income.

When a school buys a set of such infrastructure equipment, they get no advice from Becta about what they should be pay for this stuff. They’re supposed to hold a mini-competition among a subset of these 16 suppliers in order to determine the price. There are all sorts of red herrings thrown in the mix, like particular support terms and the number of times the phone is allowed to ring before it gets picked up by their answer machine, but the big problem is there are no prices listed anywhere. That’s what the bureaucracy is covering up. It’s about money and profit. It’s about making a complicated system with the express effect of not providing value for money, because that’s what profits inevitably are.

We see the same thing with taxis in the city. What Becta provides here is like a taxi licensing system for a city where they then say “just to ask the driver what he’d like to charge for our ride, and then pick the best price one that comes past”. Funny how in many cities, like Liverpool, the taxi fares are regulated. Some of the taxis have extras, like TVs in the back, and maybe they get more rides by looking good and keeping the seats clean — all for the same price. No one gets ripped off and the taxis have to work to get their money. The advisers who drew up this system must have known of these economic effects, but advised against it probably because they didn’t like this effect.

Anyhow, here is the letter I got back from my request, and here is the 132 page contract itself.

Tuesday, October 24th, 2006 at 5:34 pm - - Machining 2 Comments »

When professional authors write pot-boilers and turn out books by the yard that don’t require much thought on their part to type out, they are doing ten finger exercises. They produce a hundred thousand words of some kind of routine adventure fantasy in three months with the same plot as the previous volume of the decology, it’s printed, and the fans buy it.

It also describes what I’m doing programming a set of optimizations to the algorithms of the kind I have written several times already. The slow version, which works, got written in an hour. Now I have to type out at great length an optimized version that produces exactly the same answer in one hundredth of the computational time.

The function in question, in this instance, is DistanceToPath. You have a toolpath — a piecewise linear path, which is nothing more than a chain of XYZ points with straight lines in between — and another point in space, and you need to calculate the shortest distance between the point and the path.

Let’s start with the distance between a point p and a straight line AB. The function goes like this:

double DistanceToLine(p, A, B)
    lam = Dot(p-A, B-a) / Dot(B-A, B-A)
    if (lam < 0)
        return sqrt(Dot(p-A, p-A))
    if (lam > 1)
        return sqrt(Dot(p-B, p-B))
    q = A + lam * (B-A)
    return sqrt(Dot(q-p, q-p))

I got much better notation than this, but since you don’t want to read my library of simple classes of vector calculations, I’m using as few functions as possible. I call my XYZ class P3. My 2D point class is called P2 and its two variables are u and v, so if I hit a P3 instead of a P2 in the code, it won’t compile. Obviously the ‘-‘-operator is overloaded between P3s, and the Dot(A, B) is the dot product of the two vectors:

double Dot(A, B)
    return A.x*B.x + A.y*B.y + A.z*B.z

The length of a vector A is sqrt(Dot(A, A)).

Now, suppose I have a piecewise toolpath represented by path, which is of type array<p3>, so we have functions like path.size() and path[i], which is the (i+1)th P3 value in the path.

Now we are ready to define the main function:

DistanceToPath(p, path)
    d = sqrt(Dot(path[0]-p, path[0]-p)
    for (i = 1; i < path.size(); i++)
        d = min(d, DistanceToLine(p, path[i-1], path[i]))
    return d

That’s the sum total of the function. So how have I expanded it up into 300 lines of code? Well, if path.size() is very big (like most toolpaths), then this is going to take a while to run, and a lot of the time will be spent calling the DistanceToLine() function on line segments that couldn’t possibly contribute the the value of d.

Optimization is possible when the call to the function DistanceToPath is not isolated, that is, it’s going to be called a billion times with the same path, but for different points. Then it pays to do some precalculation.

Here is the simplest boxing strategy (sometimes known as bucketing).

Create the class:

class strip
    int i0, i1; 
    double xlo, xhi; 

And do the following precalculation to create an array of these strips:

    strips = array<strip>[(path.size() - 1) / 10 + 1];
    for (int i = 1; i < path.size()
        s = i / 10
        if (s * 10 + 1 == i)
            strip[s].i0 = i-1
            strip[s].xlo = path[i-1].x
            strip[s].xhi = path[i-1].x
        strip[s].i1 = i
        strip[s].xlo = min(strip[s].xlo, path[i].x)
        strip[s].xhi = max(strip[s].xhi, path[i].x)
    return strips

This simply divides up the path into groups of 10 line segments and records the range in the X-coordinate which they span. Now we can write the possibly 10 times faster version of the function based on this precalculation, which goes like:

DistanceToPath(p, path, strips)
    d = sqrt(Dot(path[0]-p, path[0]-p)
    for (s = 0; s < strips.size(); s++)
        if ((p.x - d <= strip[s].xhi) and (p.x + d >= strip[s].xlo))
            for (i = strip[s].i0 + 1; i < = strips[s].i1; i++)
                d = min(d, Distance(p, path[i-1], path[i])
    return d

All it does is skip over the grouped sections in the path which are too far away from the point to make a contribution to the result.

The whole idea is very simple, but to explain it in code this way has required a huge simplification of what I have actually put in the real implementation, and it still looks terrible. Hence all this finger exercising to turn what is a straightforward idea into code. Someone ought to sort this problem out and develop a notation to communicate it properly.

There are some real questions that could be studied with some statistical geometry. In this example I have boxed up the path in groups of 10 and made them into strips. I could have made a range in y as well as x, but it would have doubled the length of this code. What number should I have used? If I picked the value 1, then strips.size() would have equalled path.size(), and DistanceToPath would have run exactly as it had before, calling the DistanceToLine function the same number of times. If I picked the value path.size(), then strips.size() would have been 1, and it would have also been the same. These two extreme values correspond to putting every line segment into its own box, or putting them all in a single box. For all values in between DistanceToLine is called fewer than path.size() times, on average, and there is an improvement.

What is the optimal value? The graph of optimization (average number of times DistanceToLine is called for a random sample of points, against the strip number), can be made, but it would require a fancy statistical model to predict and model what’s going on.

An alternative boxing scenario is to use fixed boxes (strips). In this case, each strip would have its xlo,xhi values set at the start, and the range values ilo,ihi would be replaced with an array<int> so that each line segment could be listed by the strips which they overlapped. Here, if you had one strip that covered the whole width of path, then it would be as before, and if you have too many narrow strips you get each line segment covering hundreds of boxes. Where is the optimum?

This is related to a common school mathematics question where you drop a pencil at random onto a wooden floor made of boards whose width equals the length of the pencil, and ask: What is the probability that the pencil will cross the line between two boards? The answer is 2/pi, and it requires you to know the integral of arccos to find it out.

Now suppose you drop a pencil of length r onto a square tiled floor where tiles are of width t. What is the average number of tiles the pencil will cross? The answer to this would be part of the study on the theory of boxing which would tell you how to choose the optimal values in these algorithms. It gets very complicated, because the line segments of a path are not random; they are chained, so the probability that one crosses the boundary of a box affects the probability that the next one will.

I haven’t done any of this. It’s what people in universities ought to be writing papers about. When I program I just throw in some values plucked out of the air, like 5mm, or 3 times the average length of a path segment, and that’s what it remains set at in the system for decades. All it takes is one university student to spot that this is a relevant problem that goes somewhere, work it out, test it, put it on the net, and we can all use it. If there was any justice, doing something like that would make it very easy to get a programming job in CADCAM, more so than good exam results.

Last week the tip of the little finger of my right hand got badly hit by the squid while playing octopush. It’s still too painful to type with.

Saturday, October 21st, 2006 at 6:13 pm - - University

Friday was a day at the psychology department. I battled with wxwidgets to get a full screen frame without any window decorations on Mac OS X, not with the desired outcome. The best I can get is a screen filling frame, but with a title bar and a ‘close window’ button at the top. Acceptable. Shame that it works as desired under windows. The other thing I looked at was using py2app to wrap up a python application that uses Python Imaging Library and wxwidgets to run on another mac. After some unsuccessful attempts I decided to upgrade python and site packages to newer versions. I upgraded python from version 2.3 to 2.4 and downloaded wxwidgets latest available version. The new site-packages installation meant I had to reinstall py2app. Success, with the latest versions py2app created mac a working application. A lot of these different packages come with their own installation tools. Ever heard of (say eazee(!))? Well, that is used for setuptools and py2app. Or python eggs? Don’t quite know what they are good for, but some got laid in my working directory.

And I had a chat with another scientist at the department about programming some experiments for her.

Thursday, October 19th, 2006 at 8:07 am - - University

On Tuesday afternoon I went to the engineering department and together with Carl rejigged the python script he uses to control their machine. We now use two python threads, one controls all moves of the motors, updates the user interface edit boxes with the current position and speed data, and also controls buttons that are pressed or unpressed automatically when the machine is rotating. We have a separation of user interface and motor control so that the user interface is always responsive. The UI passes requests for movements through a queue to the motor thread.

In the past we could use just one thread because we always ever had to handle one request for the motors to move. The calls to the DLL for the controller card always return immediately, the controller maintains it’s own motion queue. But we had to implement sequences of movements of different speeds and pauses. The queueing system we have now in place in the python thread allows that now easiy.

Thursday, October 12th, 2006 at 7:10 pm - - Whipping 2 Comments »

You’ll be disappointed to learn that none of it was machining related — I’m still waiting for enthusiastic collaborators to fix up the pages on Pencil milling and Raster passes.

It all started with a blog posting that caused me to write up the Talbot Street bomb-making haul which happened last week not far from here and involved what police believe was the largest haul of bomb related chemicals ever discovered in someone’s home in this country. At the same time in another house they discovered rocket launchers, chemicals, and a nuclear biological suit. But since the suspects are merely white guys with “some kind of masterplan”, they are not classed as terrorists, so they get filed under the List of terrorist-like incidents that were not designated as terrorism and were entirely ignored by the national press. Terrorism, it seems, is what they say it is. There is no definition. It’s a common pattern: in 1985, Tony Lecomber, also a Nazi, was caught with 10 grenades in his house after he tried to carry a nailbomb to the offices of the Workers’ Revolutionary Party. He was also not a terrorist; he was simply misusing explosives.

That took until lunchtime. I went for lunch and looked in the paper, only to find that the Prime Minister-in-Waiting, Gordon Brown, had made a stupidly long blathering speech about about “Meeting the Terrorist Challenge” using the tool of financial sanctions. Obviously, Climate change and the Disaster recently determined massive mortality in Iraq aren’t as important to him as this BS.

As author of the wikipedia article on the Financial Sanctions Unit wikipedia article, I had to check it out.

Before that, I wasted several hours doing the rounds of my other favourite terrorism pages, and found a new fact relating to the Forest Gate Raid where 2 million quid of police money was blown chasing a ridiculous suicide chemical vest weapon. It seems that this farce was tipped off by the victim of an earlier terrorist prosecution who had been sent down for 6 years for having in his possession a blank-firing gun, DVDs of Osama bin Laden, and the address of a decorated British soldier whom he was supposedly planning to hunt down and kill. The actual conviction was for possessing information “likely to be useful to a person committing or preparing an act of terrorism” (eg the time of day). His defence lawyer said that the man was “utterly incompetent” and had an IQ of 64. The same description could be used for the policework that lead to the initiation of Operation Volga.

So, I finally got round to looking at Gordon Brown’s speech, where he applauded the fact that he had just won a Judicial Review that decided that he could restrict the payments of any benefits made to listed terrorist suspects and their households. The case had been brought by three of the suspects wives none of whom are accused of being associated with terrorism. The report doesn’t say who these people are, but they are quite possibly be related to the ones who are held in prison on charges related to the 2006 transatlantic aircraft plot. I fixed a few links in the article to reach the main New York Times story that we in England are for some reason banned from seeing.

Remember that one? It was the ring of islamofascists (President Bush’s words), some of whom didn’t have passports, who were accused all over the media of plotting to bring down 10 planes over the Atlantic using the chemicals contained in shampoo bottles. According to Gordon Brown, the police hauled in “200 mobile phones, 400 computers, and a total of 8,000 CDs, DVDs and computer disks, containing 6,000 gigabytes of data” relating to the case. Sounds like a PC warehouse. The suspects were armed with six terabytes, and the police require up to 90 days to go through it all to find out which kilobyte in it is the one that can be mixed with a stick of deodourant to produce a high explosive. The trial is not due to start till January 2008, probably because there is an embarrassing lack of evidence. Unlike with the case of the “not a bomb factory” referred to at the start of this article.

So this brought me on to the Terrorism Act 2006 page, which is a complete disaster area in terms of informational layout. But it’s 8pm now and I haven’t got all week to fix it up. Time to wind up this day. Code written: 0 lines.

Thursday, October 12th, 2006 at 7:01 pm - - University

I did some work in the engineering department of Liverpool University today. Some time ago Carl did a write up of something we had programmed to print undistorted images with one or more rotating print heads, assembled in a row. The inkjet print heads they use are meant for normal printing with paper moving rectangular to the print width. But in their machine the medium to print rotates underneath the print head, with one side of the head closer to the centre of rotation than the other. So, a rectangular bitmap would be distorted to a pie wedge. We wrote a little algorithm that transforms a bitmap into a new bitmap that, when printed on this setup, prints undistorted.
I had read it on the train last night and had a few comments and suggestions to make it clearer what this does.

Then looked into extending the controller of the machine that performs these rotations. In order to shine a light on the same area on the print medium for a specified time they want to be able to stop the rotation, then start it again, and so on. We use a python thread that monitors the machine position and when it has reached the target of the rotation joins the main thread that in turn can sleep for the specified time, then start the motion again.

I had hoped we could use some sort of callback mechanism in the DLL that controls the digital controller card: When a motor has reached it’s target position we get a user specifiable callback. We had found something in the documentation for the DLL and started coding. But we got stuck and had to call the support phone line for the card manufacturer. The friendly support person told us we were following a red herring: The documentation we had used was for a different card, using a different (probably real-time) operating system.

Last week I also spend a day there:
We had looked into rewriting the user interface of the motion controller: The old user interface got out of hand, partly because a master student had used unsuitable GUI code generators on it (python glade). We had decided to shelve this code and write a much simpler new interface. Now that this motion controller has been in use for more than a year we could also reduce the functionality to what was really needed.

Another half day last week was spent in the department of psychology. I am working on a framework to programme visual perception experiments using python, wxwidgets and python image library (PIL) on a mac os x system. More about that some other time.

Sunday, October 8th, 2006 at 10:34 am - - Machining 1 Comment »

The article which everyone should have read is The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software.

Summary: Due to heat and speed of light limits, micro-processors are no longer going to double in speed every 18 months. However, they will continue to double in density for a while, so you will start to see 2, 4, 8 or 100 processors (or cores) running on a chip in the future. If you expect the code you are writing today to remain relevent, you need to take account of this in the code you write today.

For many CAM algorithms, there’s no excuse for not using multi-cores, since users can do it for themselves already.

Take raster passes algorithm (note to readers: do something about that page!), for example. If the software cripple (I beg your pardon, “license agreement”) permits you to, you can run two copies of your CAM system, and set the first generating raster passes on the left half, and the second doing raster passes on the right half of the model. Use the time saved to load both tape files into the same text editor and merge them.

I wonder why no one did this with two computers in the old days when calculations used to take hours.

The parallelism in the raster passes algorithm is obvious, and should be automatic, although it might take a bit of reprogramming if the code was written with no consideration for such developments. For those who are interested in taxonomies, this is MIMD type parallelism, the most general kind.

Almost all machining algorithms could be subject to a sort of MISD style, or a pipeline. We see this already in systems with visualization where the first processor is generating the passes, and a second (sometimes the “graphics” processor) is plotting them up on the screen as they get finished. Instead of this, the second processor could use its time doing the linking and post-processing, so that the front part of the tape file gets saved onto the disk before the computation is complete.

Even better, the machine tool could be set running as this tape file comes out. That way it wouldn’t be necessary for the CAM system to generate toolpaths faster than they could be cut. Unfortunately these days users want instant performance; they want to see the toolpaths that will take 1 hour to actually cut, complete and on their screens within 10 seconds of selecting the tool size. It’s a bit ridiculous. Maybe longer computation times will give better results, like finite element analysis. There ought to be a quick and easy way of checking the quality of the result, but there isn’t yet. I should write and ask if Machineworks could make something that users could download for free that would enable them to benchmark their CAM systems.

Unfortunately, that’s not where we are now. For want of a better metric, users judge the software on the speed of calculation. This makes a bit of sense, if you accept that there are good programming teams and bad (or at least under-resourced) programming teams, and that if you can’t write software that runs as fast as anyone else’s, then you’re probably a bad programming team whose toolpaths aren’t going to do too well either.

This is not what I hear, but it could be true because if there was a counter-example (bad software that ran really fast), they would make exceptions.

Anyway, the important fact is that everyone is going to have to start making their algorithms parallelizable, especially as it’s something that users are going to be able to see for themselves once they learn how to use the Windows Task Manager — the little green graph of CPU usage locked at 50%, or even 25% on a four core machine: not good.

The problem is it’s going to be expensive to convert some CAM systems to run like this. I only know the code inside Depocam/Machining Strategist, and the two basic algorithms that the problem is going to be with are Scallop (which includes the much dreaded rest area detection) and Pencil milling. I certainly wasn’t interested in multithreading at the time wrote those, and I may have made a couple of arbitrary choices early that will take months of expensive developer’s time to unpick. It’s like packing a bag and putting the toothbrush at the bottom. Very inconvenient and unnecessary to have put it there, but it’s too late now. Maybe they have already made the substantial investment; I don’t know. No one’s asked for advice.

Anyway, the news is we think we’ve worked out how to parallelize all our new versions of these algorithms, except the Adaptive Clearing one. Until we get access to some multi-core machines, we won’t know if it is sound or makes a substantial difference in performance. It’s possible to fail by having the multiple calculations clashing with one another such that they’re busy all the time exchanging partial results between themselves, rather than getting any work done. In the meantime, we’re going to buy a copy of VTune which Martin is at present teaching himself how to use.

News from a week ago: Quad-core processor forecast.

Friday, October 6th, 2006 at 12:15 pm - - Whipping 1 Comment »

For statistical purposes the country has been divided into small blocks of land called Output Areas. These allow us to look in more detail at smaller local areas. Output Areas have been combined to form two layers of Super Output Areas known as Lower Layer Super Output Areas (LSOAs) and Middle Layer Super Output Areas (MSOAs)
Quoted from here

I live in an area of Liverpool that has been a ‘Neighbourhood Renewal Area’ for a number of years now. There’s a long (more than 20 years) history behind it:
The Granby area of Toxteth had it’s share of rioting back in the 1980’s and also later. It was about mainly black youth being fed up with the police harassing them for no other reasons than their skin colour. I don’t know too much about the housing situation back then. One problem must have been that ‘slum landlords’ neglected the houses, only interested in the rent they could squeeze from people at the bottom rank of the social ladder. People who cared tried to change this by getting the authorities to use compulsory purchase orders (CPO) against irresponsible landlords to take these houses into public ownership and improve living conditions. CPOs had not been used like this before, they were meant for road building, for airports and so on. Now these houses were given to housing associations who gave them to tennants that needed the social welfare system to find somewhere to live. Houses and living conditions were improved.
But over the years the area became more and more a dumping ground for people who were not wanted in other, more afluent, areas of the city. Eventually plans emerged to demolish the whole area and build something new. The housing associations were all for it and stopped using the houses for tennants. Instead the houses were tinned up, after stripping them of pipes, light fittings, toilets, sinks… things that you need to live in a house. Windows were smashed, roof windows left the inside open to the destructive forces of wind, rain and pigeons.
Deteriortation of the area was sped up and with the empty houses came other problems: Squatters, drug abuse, fly tipping…

pic of house in Cairns Street
But times have changed and my neighbourhood is trying to leave the bad reputation it still has, not just in Liverpool, behind. The few neighbours left are really nice people, there is a sense of community. We have window boxes with flowers in front of the houses, including the empty ones. We even won an award in the North West in Bloom competition for Improvement. My neighbour from opposite goes round and clandestinely paints butterflies on to the boarded up windows of empty houses. She calls the tinned up houses voids.
There are now four streets left, and the latest scheme to take away the houses is called Housing Market Renewal Initiative. The people who live here, including me, want to keep their houses. We have to fight the plans of a developer called Lovell, a company liked by Liverpool City Council and chosen to be their preferred developer for Granby Toxteth. The other day was a meeting of the ‘Three Parks Neighbourhood Committee’ where the residents organised in the Granby Residents Association were allowed to make a presentation about the effects the plans already have and will have on us. While trying to find what this committee actually does I came across the quote on top. The meeting went well, we got applause and the councillors present made the right noises signalling that they are sympathetic to our cause. But the decisions are made somewhere higher up, we are waiting for the executive board of the council to approve the plans Lovell has presented. Then the next stage in the fight to keep our houses will start.

Sunday, October 1st, 2006 at 9:26 pm - - Whipping

Last Wednesday I got up at 6am to catch the train to Manchester in order to join some IPPR fringe breakfast meeting relating to the Labour Party Conference entitled “Ready for the e-generation? Digital inclusion and active citizenship in a networked age”. I had asked to be invited on the basis of my work with Publicwhip — an obvious incident of active citizenship in the networked age.

No one was particularly interested in what I had to say.

Around the table were representatives from various citizen groups, publically funded enterprises such as uk-online, overpriced educational IT suppliers, and evil corporations like Microsoft.

The meeting ran like a Parliamentary debate: the minister, Pat McFadden MP, Parliamentary Under-Secretary for the Cabinet Office, waffles on for half an hour, then the chair goes round the table so everyone gets to say something of what they want, and finally the minister sums up with more waffle, answering whatever points that he wants to address.

A lot of it was about social exclusion and getting deaf people to use the internet to access government services. One of the success stories, which several representatives referred to, was the 38 million quid DVLA website (no, I can’t tell where that number comes from) that allows busy housewives to pay their car tax online. Apparently this benefits 30 million people in the country who are car drivers. One of the consultants said this was a great success and a sign that the government needs to commit seriously more funds to all parts of IT. As usual, I can’t account for the quoted costs to within a factor of a thousand.

The point I made, which no one found interesting, was that the government may want active citizenship, but only in limited domains. It certainly is not interested in hearing what people have to say about the this country’s foreign affairs policy, or whether we continue to pose a threat to the existence of human life with our nuclear weapons.

If I had thought of it — which I didn’t, as usual — I would have referred to the car tax service and asked if, on the same website, they could list the total tax take through the vehicle licenses as well as the spend on maintenance road by road on a map so we all knew where said money was going. The information is available. Is this not somthing the public ought to be informed of when cash is demanded?

There was also the usual reference to the MPs gaming the system and asking more written questions and creating extra cost as a side-effect in order to prove their rankings. Not only is this an unproven allegation — the stats are all available on the site waiting for someone to actually analyze them as opposed to just talk about it — but it’s the number of questions that are properly answered that matter. If I had thought of it — which I also didn’t — I would have come prepared with the following Parliamentary question:

Michael Weir MP: To ask… what the value was of each IT contract awarded by the Prime Minister’s Office in each of the last five years; and who the contractor was in each case.

Patrick McFadden MP: The Prime Minister’s Office is an integral part of the Cabinet Office. The information for the Department cannot be produced in the form requested without incurring disproportionate cost…

My considered opinion is that the government has taken to creating a market for citizen interaction with their services on their terms. There is literally billions of pounds of public money pouring into it, although none of it will be available for projects that could hold them accountable, threaten their authority, or question their policies. So my comment to the Minister could have been completely correct in every possible way, but no one would care because they are there to find out what the government is intending to spend our money on in order to satisfy those contracts and make a living. It has nothing about what’s useful.

Almost by definition, worthwhile examples of active on-line citizenship will not be funded by the government, except by accident. This is not because the government is bloated, inefficient, and wrong — which is a common right-wing position — it’s that those who control the government will automatically cause it to serve their interests. If we want to get the accounts, we’ll have to do it ourselves.

Back to normal service shortly. Meantime, I’ve just got the Ministerial Whirl working again.