Month: October 2024

Marc Hannah and the graphics pipeline

Film and projectors
Image by Gerd Altmann from Pixabay

What do a Nintendo games console and the films Jurassic Park, Beauty and the Beast and Terminator II have in common? They all used Marc Hannah’s chips and linked programs for their amazing computer effects..It is important that we celebrate the work of Black Computer Scientists and Marc is one who deserves the plaudits as much as anyone as his work has had a massive effect on the leisure time of everyone who watches movies with special effects or plays video games – and that is just about all of us.

In the early 1980s, with six others, Marc founded Silicon Graphics, becoming its principal scientist. Silicon Graphics was a revolutionary company, pioneering fast computers capable of running the kind of graphics programs on special graphics chips that suddenly allowed the film industry to do amazing special effects. Those chips and linked programs were designed by Marc.

Now computers and games consoles have special graphics chips that do fast graphics processing as standard, but it is Marc and his fellow innovators at Silicon Graphics who originally made it happen.

It all started with his work with James Clark on a system called the Geometry Engine while they were at Stanford. Their idea was to create chips that do all the maths needed to do sophisticated manipulation of imagery. VLSI (Very Large scale Integration), whereby computers were getting smaller and fitting on a chip was revolutionising computer design. Suddenly a whole microprocessor could be put on a single chip because tens of thousands (now billions) of transistors could be put on a single slice of silicon. They pioneered the idea of using VLSI for creating 3-D computer imagery, rather than just general-purpose computers, and with Silicon Graphics they turned their ideas into an industrial reality that changed both film and games industries for ever.

Silicon Graphics was the first company to create a VLSI chip in this way, not to be a general-purpose computer, but just to manipulate 3-D computer images.

A simple 3D image in a computer might be implemented as the vertices (corners) of a series of polygons. To turn that into an image on a flat screen needs a series of mathematical manipulations of those points’ coordinates to find out where they end up in that flat image. What is in the image depends on the position of the viewer and where light is coming from, for example. If the object is solid you also need to work out what is in front, so seen, and what behind, so not. Each time the object, viewer or light source moves, the calculations need to be redone. It is done as a series of passes doing different geometric manipulations in what is called a geometry pipeline and it is these calculations they focussed on. They started by working out which computations had to be really fast: the ones in the inner most loops of the code that did this image processing, so was executed over and over again. This was the complex code that meant processing images took hours or days because it was doing lots of really complex calculation. Instead of trying to write faster code though, they instead created hardware, ie a VLSI chip, to do the job. Their geometry pipeline did the computation in a lightening fast way as it was avoiding all the overhead of executing programs and instead implementing the calculations that slowed things down directly in logic gates that did all that crucial maths very directly and so really quickly.

The result was that their graphic pipeline chips and programs that worked with them became the way that CGI (computer generated imagery) was done in films allowing realistic imagery, and were incorporated into games consoles too, allowing for ever more realistic looking games.

So if some amazing special effects make some monster appear totally realistic this Halloween, or you get lost in the world of a totally realistic computer game, thank Marc Hannah, as his graphics processing chips originally made it happen.

– Paul Curzon, Queen Mary University of London

More on …

Magazines …

Front cover of CS4FN issue 29 - Diversity in Computing

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Claude Shannon: Inventing for the fun of it

Image by Paul Curzon

Claude Shannon, inventor of the rocket powered Frisbee, gasoline powered pogo stick, a calculator that worked using roman numerals, and discoverer of the fundamental equation of juggling! Oh yeah, and founder of the most important theory underpinning all digital communication: information theory.

Claude Shannon is perhaps one of the most important engineers of the 20th century, but he did it for fun. Though his work changed the world, he was always playing with and designing things, simply because it amused him. Like his contemporary Richard Feynman, he did it for ‘the pleasure of finding things out.’

As a boy, Claude liked to build model planes and radio-controlled boats. He once built a telegraph system to a friend’s house half a mile away, though he got in trouble for using the barbed wires around a nearby pasture. He earned pocket money delivering telegrams and repairing radios.

He went to the University of Michigan, and then worked on his Masters at MIT. While there, he thought that the logic he learned in his maths classes could be applied to the electronic circuits he studied in engineering. This became his Masters thesis, published in 1938. It was described as ‘one of the most important Master’s theses ever written… helped to change digital circuit design from an art to a science.’

Claude Shannon is known for his serious research, but a lot of his work was whimsical. He invented a calculator called THROBAC (Thrifty Roman numerical BACkward looking computer), that performs all its operations in the Roman numeral system. His home was full of mechanical turtles that would wander around, turning at obstacles; a gasoline-powered pogostick and rocket-powered Frisbee; a machine that juggled three balls with two mechanical hands; a machine to solve the Rubik’s cube; and the ‘Ultimate Machine’, which was just a box that when turned on, would make an angry, annoyed sound, reach out a hand and turn itself off. As Claude once explained with a smile, ‘I’ve spent lots of time on totally useless things.’

A lot of the early psychology experiments used to involve getting a mouse to run through a maze to reach some food at the end. By performing these experiments over and over in different ways, they could figure out how a mouse learns. So Claude built a mouse-shaped robot called Theseus. Theseus could search a maze until he solved it, and then use this knowledge to find its way through the maze from any starting point.

Oh, and there’s one other paper of his that needs mentioning. No, not the one on the science of juggling, or even the one describing his ‘mind reading’ machine. In 1948 he published ‘A mathematical theory of communication.’ Quite simply, this changed the world, and changed how we think about information. It laid the groundwork for a lot of important theory used in developing modern cryptography, satellite navigation, mobile phone networks… and the internet.

– Paul Curzon, Queen Mary University of London.

More on …

Related Magazine …

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

The logic of Queens

A corner of a Queens Puzzle
A corner of a Queens Puzzle: Image by Paul Curzon

Queens is a fairly simple kind of logic puzzle found for example on LinkedIn as a way to draw you back to the site. Doing daily logic puzzles is good both for mental health and to build logical thinking skills. As with programming, solving logic puzzles is mostly about pattern matching (also a useful skill to practice daily) rather than logic per se. The logic mainly comes in working out the patterns.

Let’s explore this with Queens. The puzzle has simple rules. The board is divided into coloured territories and you must place a Queen in each territory. However, no two Queens can be in the same row or column. Also no two Queens can be adjacent, horizontally, vertically or diagonally.

If we were just to use pure logic on these puzzles we would perhaps return to the rules themselves constantly to try and deduce where Queens go. That is perhaps how novices try to solve puzzles (and possibly get frustrated and give up). Instead, those who are good at puzzles create higher level rules that are derived from the basic rules. Then they apply (ie pattern match against) the new rules whenever the situation applies. As an aside this is exactly how I worked when using machine-assisted proof to prove that programs and hardware correctly met their specification, doing research into better ways to ensure the critical devices we create are correct.

Let’s look at an example from Queens. Here is a puzzle to work on. Can you place the 8 Queens?

An initial Queens puzzle - an 8x8 grid with 8 territories marked out
mage by Paul Curzon
The same puzzle with squares in one column ruled out as places for a Queen
mage by Paul Curzon

Where to start? Well notice the grey territory near the bottom. It is a territory that lives totally in one column. If we go to the rules of Queens we know that there must be a Queen in this territory. That means that Queen must be in that column. We also know that only one Queen can be in a column. That means none of the other territories in that column can possibly hold a Queen there. We can cross them all out as shown.

In effect we have created a new derived inference rule.

IF a territory only has squares available in one column 

THEN cross out all squares of other territories in that column

By similar logic we can create a similar rule for rows.

Now we can just pattern match against the situation described in that rule. If ever you see a territory contained completely in a row or column, you can cross out everything else in that row/column.

In our case in doing that it creates new situations that match the rule. You may also be able to work out other rules. One obvious new rule is the following:

IF a territory only has one free space left and no Queens 

THEN put a Queen in that free space
The same puzzle with squares in two more columns ruled out as places for two more Queens
mage by Paul Curzon

We can derive more complicated rules too. For example, we can generalise our first rule to two columns. Can you find a pair of territories that reside in the same two columns only? There is such a pair in the top right corner of our puzzle. If there is such a situation then as both must have a Queen, between them they must be the territories that provide the Queens for both those two columns. That means we can cross out all the squares from other territories in those two columns. We get the rule:

IF two territories only have squares available in two columns

THEN cross out all squares of other territories in both columns

Becoming good at Queens puzzles is all about creating more of these rules that quickly allow you to make progress in all situations. As you apply rules, new rules become applicable until the puzzle is solved.

Can you both apply these rules and if need be derive some more to pattern match your way to solving this puzzle?

It turns out that programming is a lot like this too. For a novice, writing code is a battle with the details of the semantics (the underlying logical meaning) of the language finding a construct that does what is needed. The more expert you become the more you see patterns where you have a rule you can apply to provide the code solution: IF I need to do this repeatedly counting from 1 to some number THEN I use a for loop like this… IF I have to process a 2 dimensional matrix of possibilities THEN I need a pair of nested for loops that traverse it by rows and columns… IF I need to do input validation THEN I need this particular structure involving a while loop… and so on.

Perhaps more surprisingly, research into expert behaviour suggests that is what all expert behaviour boils down to. Expert intuition is all about subconscious pattern matching for situations seen before turned into subconscious rules whether expert fire fighters or expert chess players. Now machine learning AIs are becoming experts at things we are good at. Not suprisingly, what machine learning algorithms are good at is spotting patterns to drive their behaviour.

Paul Curzon, Queen Mary University of London

More on …

Magazines …

Front cover of CS4FN issue 29 - Diversity in Computing

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos

Byte Queens

Women have made vital contributions to computer science ever since Ada Lovelace debugged the first algorithm for an actual computer (written by Charles Babbage) almost 200 years ago (more on CS4FN’s Women Portal). Despite this, women make up only a fraction (25%) of the STEM workforce: only about a fifth of senior tech roles and only a fifth of computer science students are women. The problem starts early: research by the National Centre for Computing Education suggests that female student’s intension to study computing drops off between the ages of 8 and 13. Ilenia Maietta, a computer science student at Queen Mary, talks about her experiences of studying in a male-dominated field and how she is helping to build a network for other women in tech.

Ilenia’s love for science hasn’t wavered since childhood and she is now studying for a master’s degree in computer science – but back in sixth form, the decision was between computer science and chemistry:

“I have always loved science, and growing up my dream was to become a scientist in a lab. However, in year 12, I dreaded doing the practical experiments and all the preparation and calculations needed in chemistry. At the same time, I was working on my computer science programming project, and I was enjoying it a lot more. I thought about myself 10 years in the future and asked myself ‘Where do I see myself enjoying my work more? In a lab, handling chemicals, or in an office, programming?’ I fortunately have a cousin who is a biologist, and her partner is a software engineer. I asked them about their day-to-day work, their teams, the projects they worked on, and I realised I would not enjoy working in a science lab. At the same time I realised I could definitely see myself as a computer scientist, so maybe child me knew she wanted to be scientist, just a different kind.”

The low numbers of female students in computer science classrooms can have the knock-on effect of making girls feel like they don’t belong. These faulty stereotypes that women don’t belong in computer science, together with the behaviour of male peers, continue to have an impact on Ilenia’s education:

“Ever since I moved to the UK, I have been studying STEM subjects. My school was a STEM school and it was male-dominated. At GCSEs, I was the only girl in my computer science class, and at A-levels only one of two. Most of the time it does not affect me whatsoever, but there were times it was (and is) incredibly frustrating because I am not taken seriously or treated differently because I am a woman, especially when I am equally knowledgeable or skilled. It is also equally annoying when guys start explaining to me something I know well, when they clearly do not (i.e. mansplaining): on a few occasions I have had men explain to me – badly and incorrectly – what my degree was to me, how to write code or explain tech concepts they clearly knew nothing about. 80% of the time it makes no difference, but that 20% of the time feels heavy.”

Many students choose computer science because of the huge variety of topics that you can go on to study. This was the case for Ilenia, especially being able to apply her new-found knowledge to lots of different projects:

“Definitely getting to explore different languages and trying new projects: building a variety of them, all different from each other has been fun. I really enjoyed learning about web development, especially last semester when I got to explore React.js: I then used it to make my own portfolio website! Also the variety of topics: I am learning about so many aspects of technology that I didn’t know about, and I think that is the fun part.”

“I worked on [the portfolio website] after I learnt about React.js and Next.js, and it was the very first time I built a big project by myself, not because I was assigned it. It is not yet complete, but I’m loving it. I also loved working on my EPQ [A-Level research project] when I was in school: I was researching how AI can be used in digital forensics, and I enjoyed writing up my research.”

Like many university students, Ilenia has had her fair share of challenges. She discussed the biggest of them all: imposter syndrome, as well as how she overcame it. 

“I know [imposter syndrome is] very common at university, where we wonder if we fit in, if we can do our degree well. When I am struggling with a topic, but I am seeing others around me appear to understand it much faster, or I hear about these amazing projects other people are working on, I sometimes feel out of place, questioning if I can actually make it in tech. But at the end of the day, I know we all have different strengths and interests, so because I am not building games in my spare time, or I take longer to figure out something does not mean I am less worthy of being where I am: I got to where I am right now by working hard and achieving my goals, and anything I accomplish is an improvement from the previous step.”

Alongside her degree, Ilenia also supports a small organisation called Byte Queens, which aims to connect girls and women in technology with community support.

“I am one of the awardees for the Amazon Future Engineer Award by the Royal Academy of Engineering and Amazon, and one of my friends, Aurelia Brzezowska, in the programme started a community for girls and women in technology to help and support each other, called Byte Queens. She has a great vision for Byte Queens, and I asked her if there was anything I could do to help, because I love seeing girls going into technology. If I can do anything to remove any barriers for them, I will do it immediately. I am now the content manager, so I manage all the content that Byte Queens releases as I have experience in working with social media. Our aim is to create a network of girls and women who love tech and want to go into it, and support each other to grow, to get opportunities, to upskill. At the Academy of Engineering we have something similar provided for us, but we wanted this for every girl in tech. We are going to have mentoring programs with women who have a career in tech, help with applications, CVs, etc. Once we have grown enough we will run events, hackathons and workshops. It would be amazing if any girl or woman studying computer science or a technology related degree could join our community and share their experiences with other women!”

For women and girls looking to excel in computer science, Ilenia has this advice:

“I would say don’t doubt yourself: you got to where you are because you worked for it, and you deserve it. Do the best you can in that moment (our best doesn’t always look the same at different times of our lives), but also take care of yourself: you can’t achieve much if you are not taking care of yourself properly, just like you can’t do much with your laptop if you don’t charge it. And finally, take space: our generation has the possibility to reframe so much wrongdoing of the past generations, so don’t be afraid to make yourself, your knowledge, your skills heard and valued. Any opportunities you get, any goals you achieve are because you did it and worked for it, so take the space and recognition you deserve.”

Ilenia also highlighted the importance of taking opportunities to grow professionally and personally throughout her degree, “taking time to experiment with careers, hobbies, sports to discover what I like and who I want to become” mattered enormously. Following her degree, she wants to work in software development or cyber security. Once the stress of coursework and exams is gone, Ilenia intends to “try living in different countries for some time too”, though she thinks that “London is a special place for me, so I know I will always come back.”

Ilenia encourages all women in tech who are looking for a community and support, to join the Byte Queens community and share with others: “the more, the merrier!”

– lenia Maietta and Daniel Gill, Queen Mary University of London

Visit the Byte Queens website for more details. Interested women can apply here.

More on …

Magazines …

Front cover of CS4FN issue 29 - Diversity in Computing
Cover of Issue 20 of CS4FN, celebrating Ada Lovelace

Subscribe to be notified whenever we publish a new post to the CS4FN blog.

This page is funded by EPSRC on research agreement EP/W033615/1.

QMUL CS4FN EPSRC logos