School of Computing

Through the Concurrency Gateway: a Challenge from the Near Future of Graphics Hardware

P.H. Welch

In Dirk Bartz, Bruno Raffin, and Han-Wei Shen, editors, Eurographics/ACM SIGGRAPH Symposium Proceedings: Parallel Graphics and Visualization 2004, pages 182-196. The Eurographics Association, June 2004.

Abstract

Aliasing problems are a major source for error in traditional imperative languages (such as C) and modern object-oriented languages (such as Java, C++ and C#). Add in concurrency and the problems compound exponentially. Improperly synchronized access to shared (i.e. aliased) resources leads to problems of race hazard, deadlock, livelock and starvation. This paper describes the binding into occam (a concurrent processing language based on CSP) of a secure, dynamic and efficient way of sharing data between parallel processes with minimal synchronization overheads. The key new facilities provided are: a movement semantics for assignment and communication, strict zero-aliasing, apparently dynamic memory allocation and automatic zero-or-very-small-unit-time garbage collection. With occam becoming available on a variety of microprocessors for GUI building, internet services and small-memory-footprint embedded products, these capabilities are timely. Lessons are drawn for concurrency back in OO languages - and especially for the JCSP ("CSP for Java") package library. The computer graphics industry, and in particular those involved with films, games and virtual reality, continue to demand more and more realistic computer generated images. The complexity of the scenes being modelled and the high fidelity required of the images means that rendering is simply not possible in a reasonable time (let alone real-time) on a single computer. Interactive ray tracing exists today, but real-time global illumination remains a major challenge. Fortunately, .computer graphics cards are developing at "Moore's law cubed" [David Kirk, Chief Scientist, nVIDIA].

Such performance increases are directly due to the inherent parallel nature of modern graphics cards. If this trend continues, they will be 100 times faster in a mere 3.5 years time, 1000 times faster in 5 years and they will be massively parallel. Unfortunately, past experiences in designing systems that can exploit parallel processors in anything beyond embarrassingly trivial ways are not encouraging. For real-time interaction with high fidelity images, the parallel processing requirements will not be embarrassingly trivial! Regular and irregular patterns of synchronisation and communication will have to be managed over networks of fine-grained (for accuracy) model components whose scale, topology and physical distribution are dynamically evolving.

This paper reviews weaknesses in our standard approaches to the design and implementation of concurrent systems and describes ways forward that are mature and practical -- both for the programmer to program and the hardware to execute. They are built on decades of research into process algebrae (CSP and the pi-calculus), but are able to preserve and exploit traditional skills and capabilities of serial software engineering and von Neumann architecture (components of which will still form the processor base of parallel systems for at least the next decade). The changes are, therefore, evolutionary rather than revolutionary -- but are nevertheless essential botn the field of graphics and for the wider Grand Challenges of computer science.

Bibtex Record

@inproceedings{2003,
author = {P.H. Welch},
title = {{T}hrough the {C}oncurrency {G}ateway: a {C}hallenge from the {N}ear {F}uture of {G}raphics {H}ardware},
month = {June},
year = {2004},
pages = {182-196},
keywords = {determinacy analysis, Craig interpolants},
note = {},
doi = {},
url = {http://www.cs.kent.ac.uk/pubs/2004/2003},
    publication_type = {inproceedings},
    submission_id = {20592_1099933499},
    editor = {Dirk Bartz and Bruno Raffin and Han-Wei Shen},
    refereed = {Yes},
    publisher = {The Eurographics Association},
    booktitle = {Eurographics/ACM SIGGRAPH Symposium Proceedings: Parallel Graphics and Visualization 2004},
    ISBN = {3-905673-11-8},
}

School of Computing, University of Kent, Canterbury, Kent, CT2 7NF

Enquiries: +44 (0)1227 824180 or contact us.

Last Updated: 21/03/2014