®
`
`
`
`UAVsUAVs
`
`LeAd PUsh for
`embedded
`sUPercomPUting
`
`Volume 7 Number 10 October 2005
`
` www.cotsjournalonline.com
`
`An RTC Group Publication
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2003, p. 1
`
`

`

`Hardware Assets
`
`Supercomputing Technology
`
`Reconfigurable Processing Design
`Suits UAV Radar Apps
`
`UAV-based radar electronics require supercomputing performance in a compact space. A
`reconfigurable computer architecture offers the compute density to fit the bill.
`
`Peter Buxa, Computer Engineer,
`Air Force Research Laboratory, Sensors Directorate
`David Caliga, Applications Technology Manager,
`SRC Computers
`
`Keeping size, weight and power down
`
`urable hardware. The algorithm was then
`benchmarked on the Compact MAP pro-
`cessor in order to demonstrate processor
`performance in a small form-factor suit-
`able for man-portable or small UAV ap-
`plications (Figure 1).
`
`Algorithm Tradeoffs
`The Spotlight Synthetic Aperture Ra-
`dar (SAR) Backprojection algorithm is con-
`sidered to be the “gold standard” of the SAR
`imaging techniques. A spotlight SAR image
`is a two- (or three-) dimensional mapping of
`received radar energy. A SAR sensor illumi-
`nates a target area with a series of linear fre-
`quency modulation pulses. The location of
`an individual scatterer is determined by mea-
`suring the range and Doppler (range rate) and
`comparing this to a central reference
`
`to a minimum has always ranked
`high for radar electronic subsys-
`tems designed for military aircraft. Now,
`with today’s emphasis on man-portable
`or small Unmanned Air Vehicles (UAVs),
`those requirements are becoming even
`more critical. Designing Synthetic Aper-
`ture Radar (SAR) capabilities into such
`form-factors requires processing architec-
`tures that are reconfigurable and capable
`of real-time processing while still fulfill-
`ing size, weight and power requirements.
`With all that in mind, engineers at
`the Air Force Research Labora-
`tory (AFRL) and SRC Computers
`sought to demonstrate the per-
`formance gain of a two-dimen-
`sional Synthetic Aperture Radar
`(2-D SAR) backprojection algo-
`rithm running on SRC’s Com-
`pact MAP processor architecture
`compared to a MATLAB and C
`implementation of the algorithm.
`Starting with a backprojection
`algorithm, originally written in
`MATLAB, the compute-inten-
`sive routines of the algorithm
`were converted into C Language
`and compiled using SRC’s Carte
`Programming
`Environment,
`which targets the MAP reconfig-
`
`the motion compensa-
`point, called
`tion point. As more pulses are used,
`the azimuth (or cross-range) resolution
`increases.
`There are several algorithms that
`have been developed to form spotlight
`SAR images. In deciding which algorithm
`to use, there is a tradeoff between compu-
`tational efficiency and imaging accuracy.
`For instance, the simplest algorithm or-
`ders the pulses into a rectangular array
`and performs a two-dimensional Fourier
`transform. However, the resultant image
`will not be very accurate, as the algorithm
`does not compensate for scatterer motion
`through the synthetic aperture. The most
`accurate image formation algorithm is the
`tomographic backprojection. The back-
`projection algorithm calculates an exact
`solution for every pixel in the
`image. However that approach
`has very high computational
`cost. There have been numer-
`ous algorithms developed that
`have acceptable accuracy with
`much less computational time
`than the backprojection al-
`gorithm. The most popular
`of these is the polar format
`algorithm.
`The polar format algo-
`rithm has low computational
`cost, but it has some limita-
`tions that make the backpro-
`jection algorithm more at-
`tractive. For instance, when
`using backprojection the user
`
`Figure 1
`
`AAI’s Shadow, shown here, is an example of the class of small
`UAVs designed to carry small payloads. Highly integrated
`SAR electronics enable such craft to perform detailed
`reconnaissance tasks.
`
`[  ] COTS Journal October 2005
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2003, p. 2
`
`

`

`MAP
`
`1400 Mbytes/s
`sustained
`payload each
`
`Controller
`11 Mgates
`
`4800 Mbytes/s
`
`Six Banks
`Dual-ported
`On-Board Memory
`(24 Mbytes)
`
`4800 Mbytes/s
`
`4800 Mbytes/s
`
`4800 Mbytes/s
`
`User Logic 1
`30 Mgates
`
`Dual-ported
`Memory
`(4 Mbytes)
`
`GPIO
`2400 Mbytes/s
`each
`
`User Logic 2
`30 Mgates
`
`(a)
`
`Figure 2 a & b
`
`Hardware Assets
`
`(b)
`
`In developing the Compact MAP form-factor, SRC engineers compressed their standard MAP processor volume to just 6 cubic inches. The
`unit contains approximately 60 million gates of user logic and has been tested to sustain a rate of 35 Gflops with 7.6 Gbytes/s of sustained
`external bandwidth. Shown here is a block diagram (a) and photo (b) of the Compact MAP.
`
`can choose any imaging grid, while
`there is only one imaging grid avail-
`able for the polar format algorithm.
`Moreover,
`the backprojection algo-
`rithm offers an intrinsic ability to add
`or subtract pulses from an image—a ca-
`pability that is unavailable in any other
`imaging algorithm.
`Despite its compute-heavy drawback,
`the backprojection algorithm is attractive
`since it produces the most accurate im-
`ages and can be customized depending
`on mission requirements. The challenge
`then is to craft a processing architec-
`ture that’s reconfigurable and capable of
`real-time processing while fulfilling size,
`weight and power requirements for man-
`portable or small UAV systems.
`
`Integrated by an Order of
`Magnitude
`In developing the Compact MAP
`form-factor, SRC engineers compressed
`their standard MAP processor by an or-
`der of magnitude down to just 6 cubic
`inches, while at the same time increasing
`its processing performance. The resulting
`
`Compact MAP contains approximately
`60 million gates of user logic and has
`been tested to sustain a rate of 35 Gflops
`with 7.6 Gbytes/s of sustained external
`bandwidth. A block diagram of the MAP
`along with a photograph of the Compact
`MAP are shown in Figures 2a and 2b. The
`Compact MAP can be either air-cooled
`or spray-cooled for harsh environments.
`The air-cooled portable system is shown
`in Figure 3.
`The 2-D SAR Backprojection algo-
`rithm written in MATLAB was developed
`by the Air Force Research Laboratory
`(AFRL) for prototyping and evaluation
`with SAR datasets. The dataset was syn-
`thetically generated using a simulated wide-
`band (7-13 GHz) complex radar backscat-
`ter, 360 degrees around a 3-D CAD model
`of a backhoe shown in Figure 4.
`The 2-D dataset for this study con-
`tained one slice at 10 degrees elevation of
`the full 3-D dataset, resulting in 5,040 1-
`D projections. After computation by the
`2-D SAR Backprojection algorithm, a 2-D
`image of 1001 x 1001 pixels was formed.
`Using a standard Intel 2.8 GHz Pentium
`
`4, one compute run of the full 2-D da-
`taset took 1.3 hours running MATLAB
`code. The study implemented the origi-
`nal MATLAB code in several forms. The
`compute performance of each implemen-
`tation was timed for comparison with the
`original MATLAB code. The resulting
`speedups are compared in Table 1.
`The imaging routine—called im-
`age_2d.mc—implemented on the MAP
`took advantage of many of the optimiza-
`tion techniques supported by the MAP
`Compiler. These optimizations included:
`spreading the computational array across
`multiple On-Board Memory Banks, using
`Block RAM arrays, using two User Logic
`Chips and overlapping DMAs with com-
`pute operations. The initial performance
`gain was 75x for the MATLAB–MAP ver-
`sion versus the original MATLAB version.
`The MAP performance of a com-
`pute loop when pipelined is one itera-
`tion of the loop every clock. The major
`consumer of computational time was the
`summation of the contributions of each
`swath to every pixel in the 2-D image.
`This summation loop took one clock per
`
`October 2005 COTS Journal [  ]
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2003, p. 3
`
`

`

`Hardware Assets
`
`Implementation
`
`Speedup
`
`Description
`
`MATLAB only
`
`1x
`
`C code only
`
`4.2x
`
`MATLAB – MAP
`
`151x
`
`C – MAP
`
`153x
`
`The MATLAB Only implementation computation time for
`the imaging routine, image_3d.m, was 99.9% of the total
`computational time.
`
`This implementation converted all of the original MATLAB
`code into the C Language. The converted imaging routine,
`image_3d.c, utilized the optimized Intel IPP FFT routine.
`
`The imaging routine, image_3d.c used in the “C Code
`Only” implementation was modified to image_3d.mc,
`and compiled to the MAP using the Carte Programming
`Environment.
`
`This implementation used the main.c from the “C Code
`Only” implementation in conjunction with the MAP imag-
`ing subroutine, image_3d.mc
`
`Table 1
`The compute performance of each implementation of the backprojection algorithm was timed for
`comparison with the original MATLAB code. The resulting speedups are compared here.
`
`image pixel for a total of 1002001 clocks.
`This compares to the time to perform the
`16K complex FFT of 22975. The image
`summation was then split across the two
`User Logic FPGAs in the MAP, giving an
`additional 2x speedup. The microprocessor
`environment used in the study was an In-
`tel 2.8 GHz P4 running Linux. The MAT-
`LAB–MAP implementation took only 28
`seconds to process all 5040 1-D lines.
`
`Using Two MAPs
`If two MAPs were to be utilized,
`the system would provide a super-lin-
`
`ear speedup of the application. The first
`MAP could compute the scaling, FFT and
`post-FFT scaling for ten swaths. These
`ten swath vectors would then be sent to
`the second MAP which would perform
`the image update using all ten vectors
`concurrently, yielding a speedup of 750x
`compared to the original MATLAB code.
`There’s a clear performance increase
`of running the SAR 2-D Backprojection
`algorithm on the SRC Compact MAP.
`Until now, use of the backprojection al-
`gorithm in a real-time SAR system was
`difficult due to onboard processing con-
`
`10/100 Base T
`Ethernet
`(on rear)
`
`External Power
`Connector
`(on rear)
`
`Battery/Aux Bay
`Access Panel
`(on rear)
`
`Auxiliary +5V
`
`Locking
`Power
`Switch
`
`SVGA
`
`Dual
`USB 2.0
`
`Status
`LEDs
`
`2 User Input &
`System Reset
`Buttons
`
`2 GPIO Ports
`
`Figure 3
`
`Extruded
`Aluminum
`Case
`
`Adjustable
`Nylon Hand
`Strap
`
`Shoulder Strap
`D Ring
`
`Front to Back
`Airflow
`
`The Compact MAP is offered in either
`air-cooled or spray-cooled enclosure
`formats for harsh environments. The air-
`cooled portable system is shown here.
`
`straints—such as size, weight and power.
`With the development of SRC’s Compact
`MAP processor, a real-time backprojec-
`tion implementation is practical, even
`onboard small UAV systems.
`LeRoy Gorham, and Lt. Mathew Lukacs
`of the Air Force Research Laboratory, Sen-
`sors Directorate were also co-authors of this
`
`article.
`
`SRC Computers
`Colorado Springs, CO.
`(719) 262-0213.
`[www.srccomputers.com].
`
`
`[  ] COTS Journal October 2005
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2003, p. 4
`
`