English
资源说明：Parallel k-D Tree Construction
# Copyright (c) 2010 University of Illinois
# All rights reserved.
#
# Developed by: DeNovo group, Graphis@Illinois
# University of Illinois
# http://denovo.cs.illinois.edu
# http://graphics.cs.illinois.edu
#
# Permission is hereby granted, free of charge, to any person obtaining a
# copy of this software and associated documentation files (the
# "Software"), to deal with the Software without restriction, including
# without limitation the rights to use, copy, modify, merge, publish,
# distribute, sublicense, and/or sell copies of the Software, and to
# permit persons to whom the Software is furnished to do so, subject to
# the following conditions:
#
# * Redistributions of source code must retain the above copyright
# notice, this list of conditions and the following disclaimers.
#
# * Redistributions in binary form must reproduce the above
# copyright notice, this list of conditions and the following disclaimers
# in the documentation and/or other materials provided with the
# distribution.
#
# * Neither the names of DeNovo group, Graphics@Illinois,
# University of Illinois, nor the names of its contributors may be used to
# endorse or promote products derived from this Software without specific
# prior written permission.
#
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
# OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
# MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
# IN NO EVENT SHALL THE CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR
# ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
# TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
# SOFTWARE OR THE USE OR OTHER DEALINGS WITH THE SOFTWARE.
ParKD README
============
Date: 2010-09-15 16:05:44 CDT
Table of Contents
=================
1 Introduction
2 How to...
2.1 Setup
2.2 Build
2.3 Running
2.4 Regression Tests
2.5 Benchmarking
3 make Target Index
4 Acknowledgements
4.1 Sponsors
4.2 Credits
1 Introduction
==============
The k-D tree is a well-studied acceleration data structure for ray
tracing. It is used to organize primitives in a scene to allow efficient
execution of intersection operations between rays and the primitives. The
highest quality k-D tree can be obtained using greedy cost optimization based
on a surface area heuristc (SAH). While the high quality enables very fast
ray tracing times, a key drawback is that the k-D tree construction time
remains prohibitively expensive. This cost is unreasonable for rendering
dynamic scenes for future visual computing applications on emerging multicore
systems. Much work has therefore been focused on faster parallel k-D tree
construction performance at the expense of approximating or ignoring SAH
computation, which produces k-D trees that degrade rendering time. Here, we
present new, faster multicore algorithms for building precise SAH-optimized
k-D trees.
This package, ParKD, contains implementations of all of SAH k-D tree
construction algorithms discussed in the paper published at High-Performance
Graphics 2010 [1]. All the implementations are written in C++ using
Intel Threading Building Blocks (tm).
Algorithm Directory
--------------------------------------------------+-------------------------
1. Serial Accel-serial
2. "Nested" parallel Accel-nested
3. "In-place" parallel Accel-inplace-AoS
4. "In-place" parallel (AoS-to-SoA [2]) Accel-inplace-SoA
2 How to...
===========
2.1 Setup
---------
* TBB configuration
ParKD uses Intel Threading Building Blocks (tm) extensively. Please modify
the Makefile.tbb_version file according to your TBB installation.
* External utilities
ParKD uses a number of external utilities. These are defined at the top of
Makefile.common.
2.2 Build
---------
Simply invoking "make" builds all the available implementations (Accel-*
directories). For every Accel-# directory, an executable named "parkd-#" is
created. The executables can be built individually as well: "make parkd-#".
debug binaries can be built by simply attaching "-debug" to the target
name, such as "all-debug", "parkd-inplace-SoA-debug", and "packer-debug".
By default, Makefile/s suppress excessive messages. To view the actual
commands executed by make, define VERBOSE variable.
> make VERBOSE=1
* packer
We found that loading the mesh files can be very time-consuming, due mostly
to their size. We include six input models (in Tests/Models/) that
consists of a few thousand triangles to over a million triangles.
Mesh # of triangles
------------+----------------
teapot.obj 2256
bunny.obj 69451
fairy.obj 171949
angel.obj 474048
dragon.obj 871414
happy.obj 1087716
Loading bigger models take considerable amount of time, by the use of
ASCII-based .obj file format. "packer" is a custom utility that converts
the .obj input file to a binary representation that can be readily loaded
by the parkd binaries. This can cut down the loading time by up to 75%,
which significantly speeds up the benchmarking process. The "packed" .obj
files are given .blob suffix.
2.3 Running
-----------
The simplest way to run a parkd binary is to simply specify the input mesh.
> ./parkd-inplace-SoA Tests/Models/teapot.blob
The parkd binary can accept both plain .obj and .blob file types.
For help:
> ./parkd-inplace-SoA -h
* Output
Here is an example output. Note that this is printed on stderr stream.
-------------------------------------------------------------------------
ParKD - In-place (SoA) version
Input mesh : Tests/Models/teapot.blob
Threads : 1
MaxDepth : 8
TIMING INFORMATION (in CPU ticks)
Start time : 57996741994251831
Mesh load finish time : +876186
Build start time : 57996741995128053
Build finish time : +21368025
In-place (SoA) TIMING INFORMATION (in CPU ticks)
Start time : 57996741995128926
Init (CreateEdges) : +2021634
Init (parallel_sort) : +3198726
Init (SetupTriangles) : +141876
Init (AoS->SoA) : +764937
Init (Total) : +6127173
Build start time : 57996742001256225
FindBestPlane time (Avg) : 1679724
NewGen time (Avg) : 22308
ClassifyTriangles time (Avg) : 148776
Fill time : 381951
Total build time : 21348666
Total build time (w/o Init) : 15221367
-------------------------------------------------------------------------
First, the header portion includes identifying marks to indicate the
implementation, the input used, the number of hardware threads used, and
finally the depth of the tree constructed.
Second portion, staring with the line "TIMING INFORMATION" shows the
implementation-independent timing statistics. Note that the numbers
starting with "+" indicates the time relative to the previous line. For
instance, in this invocation, the input mesh was loaded in 876186 CPU
ticks.
Title Description
-----------------------+-----------------------------------
Start time At the beginning of execution
Mesh load finish time Right after the input processing
Build start time At the implementation entry point
Build finish time At the implementation exit point
(Build finish time) - (Build start time) represents the run time of the
implementation function perceived from outside.
The last portion contains the implementation-dependent timing
statistics. More detailed information on each item can be found in later
sections of this document.
2.4 Regression Tests
--------------------
"make check" works as expected, invoking internal self-tests. Models used by
the self-tests can be configured by changing the "TEST_MODELS" variable
found in Makefile.common.
2.5 Benchmarking
----------------
Currently, the x86-specific "rdtsc" instruction is used to measure
timing. rdtsc instruction returns an unsigned 64-bit integer that represents
the number of CPU ticks since boot.
The number of hardware threads used for benchmarking purposes can be
configured by changing the "BENCH_THREADS" variable found in
Makefile.common.
The input meshes used can also be configured using the "MODELS" variable
found in Makefile.common.
* TODO Quick run (benchmark) - overall scalability analysis
Under development.
* Detailed timing (benchmark-csv) - csv output
Gathering more detailed, per-phase timing information can be achieved by
"make benchmark-csv". For each implementation, this runs the parkd binary
using varied number of threads ("BENCH_THREADS") for all the specified
inputs. The result is a set of .csv files, one per model, that contains a
detailed, per-phase timing information, a line per invocation (threads).
3 make Target Index
===================
-----------------+------------------------------------------------
all, all-debug Build all targets
parkd-* + packer
-----------------+------------------------------------------------
parkd-*(-debug) Build the parkd executable using the
implementation found in Accel-* directory
packer(-debug) Build packer executable
dev(-debug) Used to build dev- targets
-----------------+------------------------------------------------
benchmark Run all benchmarks
benchmark-* Run benchmark using Accel-* only
benchmark-csv Create .csv output for all implementations
benchmark-csv-* Create .csv output using Accel-* only
-----------------+------------------------------------------------
check Run regression tests for all implementations
check-* Run regression tests for Accel-* only
-----------------+------------------------------------------------
clean Clean all the executables and .o files
clean-results Clean up regression test and benchmark results
clean-models Clean up uncompressed and packed input files
clean-all clean + clean-results + clean-models
4 Acknowledgements
==================
4.1 Sponsors
------------
This work was funded by the Universal Parallel Computing Research Center at
the University of Illinois at Urbana-Champaign
[http://upcrc.illinois.edu]. The Center is sponsored by Intel Corporation and
Microsoft Corporation.
4.2 Credits
-----------
This software was developed by Byn Choi, Rakesh Komuravelli, Victor Lu, Hyojin
Sung, and Robert L. Bocchino, who are members of DeNovo group and Graphics
group at University of Illinois, Urbana-Champaign.
[1] Byn Choi, Rakesh Komuravelli, Victor Lu, Hyojin Sung, Robert
L. Bocchino, Sarita V. Adve, John C. Hart "Parallel SAH k-D Tree Construction"
Proceedings of High-Performance Graphics (HPG), June, 2010
[2] "Array-of-Structs to Struct-of-Arrays" optimization
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
