Page 28 - 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. 28
GRAPH EXECUTION Figure 5 shows an example image generated with our system.
Rendering and compositing of elements in the picture was
During execution, each operation gets a parameter, which made entirely using our system.
tells it for which moment in time (t ∈ N0) it should per-
form that operation. This is useful in graphs that generate Figure 5: George, I think we’re lost.
animations, in which case t represents the frame of the ani-
mation. 8. CONCLUSION
The currently implemented ways of executing a data-flow The main goal was to create a generalised and flexible soft-
graph are: ware package for performing arbitrary operations on any
data using a data-flow approach. To this end we developed
• single execution — executes the graph only once for a system for parallel execution of data-flow graphs with its
a given t own domain-specific language, created to facilitate the im-
plementation of graph operations. As an example of the sys-
• multiple execution — executes the graph for many tem’s flexibility, we implemented various compositing, ren-
given t’s dering, and general image processing operations [3].
• continuous execution — executes the graph until Although the system is already in a usable state, many fu-
interrupted by the user (t starts at 0 and rises mono- ture improvements could be made. Implementing a graph-
tonically). ical user interface for creating graphs would be most ben-
eficial, as it would make the system more accessible and
To execute the graph, we convert operations within it into easier to use. The scheduler could be improved to handle
tasks for our batch job scheduler and set their priorities ac- distributed scheduling.
cording to the dependencies from the graph.
The system gets more useful as more operations are added.
4 Possible areas for future development of operations include:
digital signal processing, computer vision, data mining, and
3 hardware control. Utilising operations from these areas, the
system could collect data from sensors, analyse it, and visu-
2 alise the results. It could also be used to control a robot or
industrial machinery.
1
9. REFERENCES
0
[1] J. W. Backus, F. L. Bauer, J. Green, C. Katz,
Figure 4: Decomposing the graph into levels. J. McCarthy, A. J. Perlis, H. Rutishauser, K. Samelson,
B. Vauquois, J. H. Wegstein, A. van Wijngaarden, and
As shown in Figure 4, we can decompose the graph into M. Woodger. Revised report on the algorithm language
levels. Operations which share the same level are mutually ALGOL 60. Communications of the ACM, 6(1):1–17,
independent and can be executed in parallel. Jan. 1963.
The parallel schedule is generated using a greedy approach, [2] R. Brinkmann. The art and science of digital
starting at the nodes with no outputs and working upward compositing. Morgan Kaufmann Publishers Inc., 1999.
to satisfy dependencies.
[3] A. Bukoˇsek. A system for parallel execution of
The batch job scheduler is currently custom-made. It spawns data-flow graphs. FRI, University of Ljubljana, 2013.
as many threads as there are processor cores in the system.
These threads then obtain work from a global priority queue, [4] M. Pharr and G. Humphreys. Physically Based
which contains the tasks. Threads with higher priority have Rendering, Second Edition: From Theory To
to finish before those with a lower one can be run. Implementation. Morgan Kaufmann Publishers Inc.,
2010.
7. OPERATIONS
[5] P. Shirley and R. K. Morley. Realistic Ray Tracing, 2nd
Implemented operations, sorted by area of usage: edition. A. K. Peters, Ltd., 2003.
• compositing [2] — CorrectGamma, Combine, Pre-
multiply, Unpremultiply, ToneMap, ChromaKey, Dif-
fKey, Resize, Crop, AffineTransform, Convolve2D
• rendering [4, 5] — Sphere, LoadTriangleMesh, Cam-
era, LoadSpectrum, BRDFMaterial, LambertianBRDF,
AshikhminBRDF, ApplyEmission, ApplyNormalMap,
SceneGraphNode, AddChild, PathTrace
• general — LoadImage, SaveImage, LoadFrame, Save-
Frame
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 28
Koper, Slovenia, 10-11 October
Rendering and compositing of elements in the picture was
During execution, each operation gets a parameter, which made entirely using our system.
tells it for which moment in time (t ∈ N0) it should per-
form that operation. This is useful in graphs that generate Figure 5: George, I think we’re lost.
animations, in which case t represents the frame of the ani-
mation. 8. CONCLUSION
The currently implemented ways of executing a data-flow The main goal was to create a generalised and flexible soft-
graph are: ware package for performing arbitrary operations on any
data using a data-flow approach. To this end we developed
• single execution — executes the graph only once for a system for parallel execution of data-flow graphs with its
a given t own domain-specific language, created to facilitate the im-
plementation of graph operations. As an example of the sys-
• multiple execution — executes the graph for many tem’s flexibility, we implemented various compositing, ren-
given t’s dering, and general image processing operations [3].
• continuous execution — executes the graph until Although the system is already in a usable state, many fu-
interrupted by the user (t starts at 0 and rises mono- ture improvements could be made. Implementing a graph-
tonically). ical user interface for creating graphs would be most ben-
eficial, as it would make the system more accessible and
To execute the graph, we convert operations within it into easier to use. The scheduler could be improved to handle
tasks for our batch job scheduler and set their priorities ac- distributed scheduling.
cording to the dependencies from the graph.
The system gets more useful as more operations are added.
4 Possible areas for future development of operations include:
digital signal processing, computer vision, data mining, and
3 hardware control. Utilising operations from these areas, the
system could collect data from sensors, analyse it, and visu-
2 alise the results. It could also be used to control a robot or
industrial machinery.
1
9. REFERENCES
0
[1] J. W. Backus, F. L. Bauer, J. Green, C. Katz,
Figure 4: Decomposing the graph into levels. J. McCarthy, A. J. Perlis, H. Rutishauser, K. Samelson,
B. Vauquois, J. H. Wegstein, A. van Wijngaarden, and
As shown in Figure 4, we can decompose the graph into M. Woodger. Revised report on the algorithm language
levels. Operations which share the same level are mutually ALGOL 60. Communications of the ACM, 6(1):1–17,
independent and can be executed in parallel. Jan. 1963.
The parallel schedule is generated using a greedy approach, [2] R. Brinkmann. The art and science of digital
starting at the nodes with no outputs and working upward compositing. Morgan Kaufmann Publishers Inc., 1999.
to satisfy dependencies.
[3] A. Bukoˇsek. A system for parallel execution of
The batch job scheduler is currently custom-made. It spawns data-flow graphs. FRI, University of Ljubljana, 2013.
as many threads as there are processor cores in the system.
These threads then obtain work from a global priority queue, [4] M. Pharr and G. Humphreys. Physically Based
which contains the tasks. Threads with higher priority have Rendering, Second Edition: From Theory To
to finish before those with a lower one can be run. Implementation. Morgan Kaufmann Publishers Inc.,
2010.
7. OPERATIONS
[5] P. Shirley and R. K. Morley. Realistic Ray Tracing, 2nd
Implemented operations, sorted by area of usage: edition. A. K. Peters, Ltd., 2003.
• compositing [2] — CorrectGamma, Combine, Pre-
multiply, Unpremultiply, ToneMap, ChromaKey, Dif-
fKey, Resize, Crop, AffineTransform, Convolve2D
• rendering [4, 5] — Sphere, LoadTriangleMesh, Cam-
era, LoadSpectrum, BRDFMaterial, LambertianBRDF,
AshikhminBRDF, ApplyEmission, ApplyNormalMap,
SceneGraphNode, AddChild, PathTrace
• general — LoadImage, SaveImage, LoadFrame, Save-
Frame
m a t c o s -1 3 Proceedings of the 2013 Mini-Conference on Applied Theoretical Computer Science 28
Koper, Slovenia, 10-11 October
