IEEE Circuits and Systems Magazine - Q2 2021 - 61
queries in complex environments without reprogramming
the accelerator during runtime.
C. Collision Detection
In the collision detection step, the planner determines
whether there are potential collisions with the environment
or the robot itself during movement. Specifically,
collision detection is the primary challenge in motion
planning, which often comprises 90% of the processing
time [165].
Several works leverage data parallelization computing
on GPUs to achieve speedup [165]-[167]. For example,
Bialkowski et al. [165] divide the RRT* algorithm
of collision detection tasks into three parallel dimensions
and construct thread block grids to execute collision
computations simultaneously. However, GPU
can only provide a constant speedup factor due to the
core limitations, which is still hard to achieve the realtime
requirement.
Recently, [168]-[170] develop high-efficiency custom
hardware implementations based on the FPGA system.
Atay and Bayazit [168] focus on directly accelerating the
PRM algorithm on FPGA by creating functional units to
perform the random sampling, nearest neighbor search
and parallelizing triangle-triangle testing. However,
this design cannot be reconfigured at runtime, and the
huge resource demands make it fail to support a large
roadmap. Murray et al. [169] present a novel microarchitecture
for an FPGA-based accelerator to speed up
collision detection by creating a specialized circuit for
each motion in the roadmap. This solution achieves
sub-millisecond speed for motion planning query and
improves the power consumption by more than one order
of magnitude, which is sufficient to enable real-time
robotics applications.
Besides real-time constraint, motion planning algorithms
also have flexibility requirements to make the
robots adapt to dynamic environments. Dadu-P [170]
build a scalable motion planning accelerator to attain
both high efficiency and flexibility, where a motion
plan can be solved in around 300 microseconds in a
dynamic environment. A hardware-friendly data structure
representing roadmap edges is adopted to achieve
flexibility, and a batched processing as well as a priority-rating
method are proposed to achieve high efficiency.
But this design comprises a 25× latency increase to
make it retargetable to different robots and scenarios
due to the external memory access. Murray et al. [164]
develop a fully retargetable microarchitecture of collision
detection and graph search accelerator that can
perform motion planning in less than 3 ms with a modest
power consumption of 35 W. This design divides
the collision detection workflow into two stages. The
SECOND QUARTER 2021
collision detection results for the discretized roadmap
are precomputed in the first stage before runtime, and
then the collision detection accelerator streams in the
voxels of obstacles and the edges of flags which are in
collision at runtime.
D. Graph Search
After collision detection, the planner will try to find the
shortest and safe path from the start position to the
target position based on the obtained collision-free
roadmap through graph search. Several works explore
graph search accelerations. Bondhugula et al. [171]
employ a parallel FPGA-based design using a blocked
algorithm to solve large instances of All-Pairs ShortestPaths
(APSP) problem, which achieves a 15× speedup
over an optimized CPU-based implementation. Sridharan
et al. [172] present an architecture-efficient solution
based on Dijkstra's algorithm to accelerate the
shortest path search, and Takei et al. [173] extend this
for a high degree of parallelism and large-scale graph
search. Recently, Murray et al. [164] accelerate graph
search with the Bellman-Ford algorithm. By leveraging
a precomputed roadmap and bounding specific robot
quantities, this design enables a more compact and efficient
storage structure, dataflows and a low-cost interconnection
network.
VI. Partial Reconfiguration
FPGA technology provides the flexibility of on-site programming
and re-programming without going through
re-fabrication with a modified design. Partial Reconfiguration
(PR) takes this flexibility one step further,
allowing the modification of an operating FPGA
design by loading a partial configuration file, usually
a partial BIT file [174]. Using PR, after a full BIT
file configures the FPGA, partial BIT files can be downloaded
to modify reconfigurable regions in the FPGA
without compromising the integrity of the applications
running on those parts of the device that are
not being reconfigured.
A major performance bottleneck for PR is the configuration
overhead, which seriously limits the usefulness
of PR. To address this problem, in [175], the authors
propose a combination of two techniques to minimize
the overhead. First, the authors design and implement
fully streaming DMA engines to saturate the configuration
throughput. Second, the authors exploit a simple
form of data redundancy to compress the configuration
bitstreams, and implement an intelligent internal
configuration access port (ICAP) controller to perform
decompression at runtime. This design achieves an effective
configuration data transfer throughput of up to
1.2 Gbytes/s, which actually well surpasses the theoretical
IEEE CIRCUITS AND SYSTEMS MAGAZINE
61
IEEE Circuits and Systems Magazine - Q2 2021
Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2021
Contents
IEEE Circuits and Systems Magazine - Q2 2021 - Cover1
IEEE Circuits and Systems Magazine - Q2 2021 - Cover2
IEEE Circuits and Systems Magazine - Q2 2021 - Contents
IEEE Circuits and Systems Magazine - Q2 2021 - 2
IEEE Circuits and Systems Magazine - Q2 2021 - 3
IEEE Circuits and Systems Magazine - Q2 2021 - 4
IEEE Circuits and Systems Magazine - Q2 2021 - 5
IEEE Circuits and Systems Magazine - Q2 2021 - 6
IEEE Circuits and Systems Magazine - Q2 2021 - 7
IEEE Circuits and Systems Magazine - Q2 2021 - 8
IEEE Circuits and Systems Magazine - Q2 2021 - 9
IEEE Circuits and Systems Magazine - Q2 2021 - 10
IEEE Circuits and Systems Magazine - Q2 2021 - 11
IEEE Circuits and Systems Magazine - Q2 2021 - 12
IEEE Circuits and Systems Magazine - Q2 2021 - 13
IEEE Circuits and Systems Magazine - Q2 2021 - 14
IEEE Circuits and Systems Magazine - Q2 2021 - 15
IEEE Circuits and Systems Magazine - Q2 2021 - 16
IEEE Circuits and Systems Magazine - Q2 2021 - 17
IEEE Circuits and Systems Magazine - Q2 2021 - 18
IEEE Circuits and Systems Magazine - Q2 2021 - 19
IEEE Circuits and Systems Magazine - Q2 2021 - 20
IEEE Circuits and Systems Magazine - Q2 2021 - 21
IEEE Circuits and Systems Magazine - Q2 2021 - 22
IEEE Circuits and Systems Magazine - Q2 2021 - 23
IEEE Circuits and Systems Magazine - Q2 2021 - 24
IEEE Circuits and Systems Magazine - Q2 2021 - 25
IEEE Circuits and Systems Magazine - Q2 2021 - 26
IEEE Circuits and Systems Magazine - Q2 2021 - 27
IEEE Circuits and Systems Magazine - Q2 2021 - 28
IEEE Circuits and Systems Magazine - Q2 2021 - 29
IEEE Circuits and Systems Magazine - Q2 2021 - 30
IEEE Circuits and Systems Magazine - Q2 2021 - 31
IEEE Circuits and Systems Magazine - Q2 2021 - 32
IEEE Circuits and Systems Magazine - Q2 2021 - 33
IEEE Circuits and Systems Magazine - Q2 2021 - 34
IEEE Circuits and Systems Magazine - Q2 2021 - 35
IEEE Circuits and Systems Magazine - Q2 2021 - 36
IEEE Circuits and Systems Magazine - Q2 2021 - 37
IEEE Circuits and Systems Magazine - Q2 2021 - 38
IEEE Circuits and Systems Magazine - Q2 2021 - 39
IEEE Circuits and Systems Magazine - Q2 2021 - 40
IEEE Circuits and Systems Magazine - Q2 2021 - 41
IEEE Circuits and Systems Magazine - Q2 2021 - 42
IEEE Circuits and Systems Magazine - Q2 2021 - 43
IEEE Circuits and Systems Magazine - Q2 2021 - 44
IEEE Circuits and Systems Magazine - Q2 2021 - 45
IEEE Circuits and Systems Magazine - Q2 2021 - 46
IEEE Circuits and Systems Magazine - Q2 2021 - 47
IEEE Circuits and Systems Magazine - Q2 2021 - 48
IEEE Circuits and Systems Magazine - Q2 2021 - 49
IEEE Circuits and Systems Magazine - Q2 2021 - 50
IEEE Circuits and Systems Magazine - Q2 2021 - 51
IEEE Circuits and Systems Magazine - Q2 2021 - 52
IEEE Circuits and Systems Magazine - Q2 2021 - 53
IEEE Circuits and Systems Magazine - Q2 2021 - 54
IEEE Circuits and Systems Magazine - Q2 2021 - 55
IEEE Circuits and Systems Magazine - Q2 2021 - 56
IEEE Circuits and Systems Magazine - Q2 2021 - 57
IEEE Circuits and Systems Magazine - Q2 2021 - 58
IEEE Circuits and Systems Magazine - Q2 2021 - 59
IEEE Circuits and Systems Magazine - Q2 2021 - 60
IEEE Circuits and Systems Magazine - Q2 2021 - 61
IEEE Circuits and Systems Magazine - Q2 2021 - 62
IEEE Circuits and Systems Magazine - Q2 2021 - 63
IEEE Circuits and Systems Magazine - Q2 2021 - 64
IEEE Circuits and Systems Magazine - Q2 2021 - 65
IEEE Circuits and Systems Magazine - Q2 2021 - 66
IEEE Circuits and Systems Magazine - Q2 2021 - 67
IEEE Circuits and Systems Magazine - Q2 2021 - 68
IEEE Circuits and Systems Magazine - Q2 2021 - 69
IEEE Circuits and Systems Magazine - Q2 2021 - 70
IEEE Circuits and Systems Magazine - Q2 2021 - 71
IEEE Circuits and Systems Magazine - Q2 2021 - 72
IEEE Circuits and Systems Magazine - Q2 2021 - 73
IEEE Circuits and Systems Magazine - Q2 2021 - 74
IEEE Circuits and Systems Magazine - Q2 2021 - 75
IEEE Circuits and Systems Magazine - Q2 2021 - 76
IEEE Circuits and Systems Magazine - Q2 2021 - 77
IEEE Circuits and Systems Magazine - Q2 2021 - 78
IEEE Circuits and Systems Magazine - Q2 2021 - 79
IEEE Circuits and Systems Magazine - Q2 2021 - 80
IEEE Circuits and Systems Magazine - Q2 2021 - 81
IEEE Circuits and Systems Magazine - Q2 2021 - 82
IEEE Circuits and Systems Magazine - Q2 2021 - 83
IEEE Circuits and Systems Magazine - Q2 2021 - 84
IEEE Circuits and Systems Magazine - Q2 2021 - 85
IEEE Circuits and Systems Magazine - Q2 2021 - 86
IEEE Circuits and Systems Magazine - Q2 2021 - 87
IEEE Circuits and Systems Magazine - Q2 2021 - 88
IEEE Circuits and Systems Magazine - Q2 2021 - 89
IEEE Circuits and Systems Magazine - Q2 2021 - 90
IEEE Circuits and Systems Magazine - Q2 2021 - 91
IEEE Circuits and Systems Magazine - Q2 2021 - 92
IEEE Circuits and Systems Magazine - Q2 2021 - 93
IEEE Circuits and Systems Magazine - Q2 2021 - 94
IEEE Circuits and Systems Magazine - Q2 2021 - 95
IEEE Circuits and Systems Magazine - Q2 2021 - 96
IEEE Circuits and Systems Magazine - Q2 2021 - 97
IEEE Circuits and Systems Magazine - Q2 2021 - 98
IEEE Circuits and Systems Magazine - Q2 2021 - 99
IEEE Circuits and Systems Magazine - Q2 2021 - 100
IEEE Circuits and Systems Magazine - Q2 2021 - 101
IEEE Circuits and Systems Magazine - Q2 2021 - 102
IEEE Circuits and Systems Magazine - Q2 2021 - 103
IEEE Circuits and Systems Magazine - Q2 2021 - 104
IEEE Circuits and Systems Magazine - Q2 2021 - 105
IEEE Circuits and Systems Magazine - Q2 2021 - 106
IEEE Circuits and Systems Magazine - Q2 2021 - 107
IEEE Circuits and Systems Magazine - Q2 2021 - 108
IEEE Circuits and Systems Magazine - Q2 2021 - 109
IEEE Circuits and Systems Magazine - Q2 2021 - 110
IEEE Circuits and Systems Magazine - Q2 2021 - 111
IEEE Circuits and Systems Magazine - Q2 2021 - 112
IEEE Circuits and Systems Magazine - Q2 2021 - 113
IEEE Circuits and Systems Magazine - Q2 2021 - 114
IEEE Circuits and Systems Magazine - Q2 2021 - 115
IEEE Circuits and Systems Magazine - Q2 2021 - 116
IEEE Circuits and Systems Magazine - Q2 2021 - 117
IEEE Circuits and Systems Magazine - Q2 2021 - 118
IEEE Circuits and Systems Magazine - Q2 2021 - 119
IEEE Circuits and Systems Magazine - Q2 2021 - 120
IEEE Circuits and Systems Magazine - Q2 2021 - 121
IEEE Circuits and Systems Magazine - Q2 2021 - 122
IEEE Circuits and Systems Magazine - Q2 2021 - 123
IEEE Circuits and Systems Magazine - Q2 2021 - 124
IEEE Circuits and Systems Magazine - Q2 2021 - 125
IEEE Circuits and Systems Magazine - Q2 2021 - 126
IEEE Circuits and Systems Magazine - Q2 2021 - 127
IEEE Circuits and Systems Magazine - Q2 2021 - 128
IEEE Circuits and Systems Magazine - Q2 2021 - Cover3
IEEE Circuits and Systems Magazine - Q2 2021 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2023Q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2022Q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021Q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2021q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2020q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2019q1
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q4
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q3
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q2
https://www.nxtbook.com/nxtbooks/ieee/circuitsandsystems_2018q1
https://www.nxtbookmedia.com