Page 25 - Krész, Miklós, and Andrej Brodnik (eds.). MATCOS-13. Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science. Koper: University of Primorska Press, 2016.
P. 25
ystem for parallel execution of data-flow graphs
Andrej Bukošek
FRI, University of Ljubljana
Vecˇna pot 113,
1000 Ljubljana, Slovenia
andrej.bukosek@gmail.com
ABSTRACT 1. INTRODUCTION
This paper describes the system we developed for performing Computer generation and manipulation of images is becom-
arbitrary operations on data in parallel using a data-flow ing more and more prevalent in the film industry [2]. From
graph [3]. compositing of complex rendered scenes with live actors to
simple colour grading, such tasks are accomplished with spe-
Each operation is implemented in a dynamically loadable cialised software that allows its users to create a data-flow
module or using a domain-specific language, which was de- graph of operations, which are applied to the footage.
signed specifically for this purpose. We also implemented
a compiler for this language. Our domain-specific language Our goal was to create a generalised and more flexible soft-
is functional and strongly typed. We designed its type sys- ware package for performing arbitrary operations on any
tem to be modular. Every data type is implemented in an data using a data-flow approach.
external dynamically loadable module, which the compiler
loads during its initialisation. Each module contains func- The core functionality of the system is the parallel execution
tions for generating an intermediate representation for the of data-flow graphs. Each node in a graph represents an
LLVM system, which optimises it and translates it into ma- operation on data, which passes through its edges.
chine code.
To ease creation of new graph operations, we developed a
As an example usage of our system, we developed operations domain-specific language. Operations can also be imple-
for image manipulation, compositing, and rendering of 3D mented in any language that supports compiling code into
scenes. Such a set of operations is commonly used in the shared objects with a standard C ABI (these plugins are
film industry for the creation of special effects. then loaded at runtime). Our domain-specific language is
functional and strongly typed. An interesting feature is its
We also implemented a renderer based on the path tracing type system. Each type is implemented in an external shared
algorithm, which creates an image from the description of object (plugin), which enables users to add custom types and
a 3D scene. This method is based on a physically-correct parsers for constant values.
simulation of light bouncing around the scene.
As a practical usage of this system, we also implemented a
Categories and Subject Descriptors variety of operations and types. A particularly interesting
operation is a 3D scene renderer, which employs the Monte
D.1.3 [Programming Techniques]: Parallel programming; Carlo path tracing algorithm to generate physically-correct
D.3.2 [Programming Languages]: Functional languages; images of 3D scenes [4, 5].
D.3.2 [Programming Languages]: Specialized applica-
tion languages; D.3.4 [Programming Languages]: Com- 2. SYSTEM ARCHITECTURE
pilers; E.1 [Data Structures]: Graphs; I.3.4 [Computer
Graphics]: Graphics packages; I.3.7 [Computer Graph- Figure 1 shows an overview of the system components.
ics]: Raytracing, Animation; I.4.0 [Image Processing and
Computer Vision]: Image processing software Task scheduler I/O modules
General Terms Script
Design, Languages, Algorithms Graph executor Operation
modules
Keywords
User interface
data-flow graphs, parallelisation, domain-specific language,
compositing, rendering, computer graphics Compiler Type modules
Supervisors Figure 1: System architecture.
Dr. Andrej Brodnik, Dr. Borut Robiˇc
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 25
Koper, Slovenia, 10-11 October
Andrej Bukošek
FRI, University of Ljubljana
Vecˇna pot 113,
1000 Ljubljana, Slovenia
andrej.bukosek@gmail.com
ABSTRACT 1. INTRODUCTION
This paper describes the system we developed for performing Computer generation and manipulation of images is becom-
arbitrary operations on data in parallel using a data-flow ing more and more prevalent in the film industry [2]. From
graph [3]. compositing of complex rendered scenes with live actors to
simple colour grading, such tasks are accomplished with spe-
Each operation is implemented in a dynamically loadable cialised software that allows its users to create a data-flow
module or using a domain-specific language, which was de- graph of operations, which are applied to the footage.
signed specifically for this purpose. We also implemented
a compiler for this language. Our domain-specific language Our goal was to create a generalised and more flexible soft-
is functional and strongly typed. We designed its type sys- ware package for performing arbitrary operations on any
tem to be modular. Every data type is implemented in an data using a data-flow approach.
external dynamically loadable module, which the compiler
loads during its initialisation. Each module contains func- The core functionality of the system is the parallel execution
tions for generating an intermediate representation for the of data-flow graphs. Each node in a graph represents an
LLVM system, which optimises it and translates it into ma- operation on data, which passes through its edges.
chine code.
To ease creation of new graph operations, we developed a
As an example usage of our system, we developed operations domain-specific language. Operations can also be imple-
for image manipulation, compositing, and rendering of 3D mented in any language that supports compiling code into
scenes. Such a set of operations is commonly used in the shared objects with a standard C ABI (these plugins are
film industry for the creation of special effects. then loaded at runtime). Our domain-specific language is
functional and strongly typed. An interesting feature is its
We also implemented a renderer based on the path tracing type system. Each type is implemented in an external shared
algorithm, which creates an image from the description of object (plugin), which enables users to add custom types and
a 3D scene. This method is based on a physically-correct parsers for constant values.
simulation of light bouncing around the scene.
As a practical usage of this system, we also implemented a
Categories and Subject Descriptors variety of operations and types. A particularly interesting
operation is a 3D scene renderer, which employs the Monte
D.1.3 [Programming Techniques]: Parallel programming; Carlo path tracing algorithm to generate physically-correct
D.3.2 [Programming Languages]: Functional languages; images of 3D scenes [4, 5].
D.3.2 [Programming Languages]: Specialized applica-
tion languages; D.3.4 [Programming Languages]: Com- 2. SYSTEM ARCHITECTURE
pilers; E.1 [Data Structures]: Graphs; I.3.4 [Computer
Graphics]: Graphics packages; I.3.7 [Computer Graph- Figure 1 shows an overview of the system components.
ics]: Raytracing, Animation; I.4.0 [Image Processing and
Computer Vision]: Image processing software Task scheduler I/O modules
General Terms Script
Design, Languages, Algorithms Graph executor Operation
modules
Keywords
User interface
data-flow graphs, parallelisation, domain-specific language,
compositing, rendering, computer graphics Compiler Type modules
Supervisors Figure 1: System architecture.
Dr. Andrej Brodnik, Dr. Borut Robiˇc
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 25
Koper, Slovenia, 10-11 October
