A Sandpaper-Like Proposal Draft

This post was published 10 months 17 days ago and as such, probably does not reflect my current opinion or ability.

Having spoken to Henry Fortuna yesterday about my new project topic, I’m feeling more confident about its suitability. It was established both that the particular problem I attempt to tackle will have a huge attempt on the project overall, and also that a simulation of characters moving in a virtual world should be a feasible situation.

Although I haven’t had as much time as I would have hoped for to construct another research question and I realise my ideas still require a lot of refinement, I have a (very) rough first draft of my proposal below. Hopefully I can re-write and revise this based on any feedback I receive. It’s all text from here on in because this is serious business – photo thanks to Daniel Conway..

Introduction

The aim of the investigation is to demonstrate how a series of computers, working in parallel, can be used to process and manage entities in a simple virtual world. Techniques to manage distribution and handle a range of tasks concurrently, as well as for dealing with scalability and fault tolerance will be considered.

Motivation

Concurrency has become more and more of a prominent issue within software development, even a necessity to make the most of modern advances in hardware (Davies and Shrout, 2009). With the majority current gaming systems sporting multiple-core CPUs (Valve Corporation, 2009) and consoles tailored towards parallel computation (Stokes, 2008), the importance and currency of this issue is particularly applicable to games programming.

However, nowhere is this issue more apparent than concerning the development of servers for Massively Multi-player Online Games. These systems must be capable of managing a range of tasks concurrently, dealing with variations in load while still maintaining a stable throughpu (Waldo, 2008). Even if it were possible to use a single machine for this endeavour, running costs alone(Atwood, 2007) make employing a variable number of distributed nodes a worthwhile consideration.

As such this specialised area of games development combines the problems of developing parallel applications with the issues of distributed computing, but unlike render farms which can take hours to produce movie frames (Christensen, P. H. et al, 2006), or scientific investigations which might extend for years at a time (SETI@home, 2009), results must be calculated in fractions of a second to allow the game to progress.

Improvements to the organisation and throughput of clusters of locally distributed machines can offer clear benefits to the scope and hardware requirements for running massively multi-player online games.

Research Question

How can the processing of a real-time virtual environment benefit from parallelisation over multiple distributed computer systems?

Addressing the Question

Initially, a simplest-solution framework will be created to allow for parallel tasks to be distributed over multiple networked systems, overseen by a central server. The desired simulation will be built on this and will involve the creation of a simple 2D environment, and characters which will be made to navigate and perform actions within it. From this point the simulation will be optimised and improved, in particular investigating whether and how load balancing can increase performance and minimise hardware requirements.

Although performance of the simulation will be measured in terms of throughput, a range of factors will be considered when evaluating the solution and simply allowing processing to occur over multiple systems should answer the question to a large extent.

Resources and Requirements

Although ideally a Beowulf cluster (Beowulf, 2009) could be set up to allow a range of existing software to be utilised, this would involve additional requirements – most notably the installation of the Linux (or another *NIX) operating system to multiple machines. There are few reasons why a similar setup could not be achieved using the Windows operating system currently installed on available lab computers. Multi-platform support could possibly be investigated through my own hardware, if suitable libraries and approaches were chosen for the project.

Although the project will focus on distributed computation, systems with multiple CPU cores should prove beneficial to the simulation. These should be available through the dual-core processors in the lab computers.

In terms of software, again the laboratory machines should provide the necessary packages, which might be supplemented with open source tools and libraries.

References

• Davies, L and Shrout, R. 2009. Who Moved the Goal Posts? The Rapidly Changing World of CPUs [online] Available from: http://www.gamasutra.com/view/feature/4168/sponsored_feature_who_moved_the_.php [Accessed October 2009]
   
• Valve Corporation. 2009. Steam Hardware Survey [online] Available from: http://store.steampowered.com/hwsurvey/ [Accessed October 2009]
   
• Stokes, J. 2008. Game Console Architecture In-Depth [online] Available from: http://arstechnica.com/hardware/news/2008/09/game-console-architecture-in-depth.ars [Accessed 2009]
   
• Waldo, J. 2008. Scaling in Games & Virtual Worlds. ACM Queue. 6(7), pp.10-16.
   
• Atwood, J. 2007. When Hardware is Free, Power is Expensive [online] http://www.codinghorror.com/blog/archives/000868.html [Accessed May 2007]
   
• Christensen, P. H. et al, 2006. Ray Tracing for the Movie ‘Cars’. In: Proceedings of the IEEE Symposium on Interactive Ray Tracing 2006, Salt Lake City USA September 18-20. IEEE. pp.1-6. [online] Available from: http://graphics.pixar.com/library/RayTracingCars/paper.pdf. [Accessed October 2009]
   
• SETI@home, 2009. [online] http://setiathome.berkeley.edu/sah_about.php[Accessed October 2009]
   
• Beowulf. 2009 [online] http://www.beowulf.org/overview/index.html [Accessed 2008]
   

Bibliography

As this is a rough draft, please see my relevant delicious links. These are missing references to books, ACM publications, journals I can/could only read within the university and older bookmarks which I have found useful, so I will attempt to update in the near future with a refined, current listing.