TECHNIQUES FOR ACCELERATING COMPUTATIONS USING FIELD PROGRAMMABLE GATE ARRAY PROCESSORS
First Claim
1. A hybrid raytracing apparatus, comprising:
- a configurable logic circuit programmable to implement a tree traversal algorithm;
an intersection processor configurable to implement a ray-triangle intersection algorithm, wherein the intersection processor is in data communication with the field programmable gate array; and
a central processor configurable to control the field programmable gate array and the intersection processor.
1 Assignment
0 Petitions
Accused Products
Abstract
Various embodiments are disclosed for accelerating computations using field programmable gate arrays (FPGA). Various tree traversal techniques, architectures, and hardware implementations are disclosed. Various disclosed embodiments comprise hybrid architectures comprising a central processing unit (CPU), a graphics processor unit (GPU), a field programmable gate array (FPGA), and variations or combinations thereof, to implement raytracing techniques. Additional disclosed embodiments comprise depth-breadth search tree tracing techniques, blocking tree branch traversal techniques to avoid data explosion, compact data structure representations for ray and node representations, and multiplexed processing of multiple rays in a programming element (PE) to leverage pipeline bubble.
66 Citations
26 Claims
-
1. A hybrid raytracing apparatus, comprising:
-
a configurable logic circuit programmable to implement a tree traversal algorithm; an intersection processor configurable to implement a ray-triangle intersection algorithm, wherein the intersection processor is in data communication with the field programmable gate array; and a central processor configurable to control the field programmable gate array and the intersection processor. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A logic element for tree traversal comprising:
at least one processor core comprising; a first input to receive a ray; a second input to receive a node; an intersecting block to determine if there is an intersection between the ray and the node, wherein the intersecting block is configured to output the node if the node is a leaf node, and wherein the intersecting block is configured to output at least one child node if the node is not a leaf node; a primary memory storage unit configurable to store the at least one child node; a secondary memory storage unit configurable to store the at least one child node; and a decision logic circuit, configurable to determine whether a node should be stored in the primary storage unit or in the secondary storage unit. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20)
-
21. A method for tree traversal, comprising:
-
receiving, by a logic circuit, at least one ray packet containing at least one ray; receiving, by the logic circuit, at least one node of a k-dimensional (KD) tree; traversing the KD tree, by the logic circuit, by performing an intersection test between the at least one ray and the at least one node; wherein if the intersection test is positive, performing, via the logic circuit, a leaf node test, wherein if the leaf node test is positive a leaf node is output; and wherein if the leaf node test is negative, calculating, by a floating point processor, two intersection intervals, wherein the intersection intervals are used by at least one child node of the at least one node for intersection tests, and wherein the at least one child node are output for continued tree traversal. - View Dependent Claims (22, 23, 24, 25, 26)
-
Specification