III: EAGER: Accelerated Filtering of Spatiotemporal Archives Using Reconfigurable Hardware

III：EAGER：使用可重构硬件加速时空档案过滤

• 批准号: 1144158
• 负责人: Vassilis Tsotras
• 金额: $ 10万
• 依托单位: University of California-Riverside
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1144158&HistoricalAwards=false
• 关键词: III; EAGER; Accelerated; Filtering; Spatiotemporal

The wide adoption of GPS and sensor technologies has created many applications that collect and maintain very large repositories of data in the form of trajectories. To better analyze such data, a user can pose complex pattern queries using a high level region-based representation that abstracts trajectories by the temporally ordered sequence of spatial regions (or areas/points of interest) they visited. For example: "find moving objects that first passed by the train station, then by the town center and were always within a mile from the harbor". Temporal and counter constraints, as well as region variables and region hierarchies can be added to create very powerful queries. Similarly, one can formulate join queries that identify pairs of trajectories with similar behavior, etc. While such pattern-based queries are critical in analyzing vast trajectory archives, traditional methods fail to scale due to the large computational effort and size of the data. Adding more resources (i.e., many processors) will not eliminate the bottleneck (each processor still uses multiple clock cycles per operation) and may also create a large communication overhead between the processors. Instead, this project takes a different, high risk-high payoff approach by using reconfigurable hardware, namely, Field Programmable Gate Arrays (FPGAs). FPGAs are code accelerators where a portion of the application is mapped as a circuit on the FPGA; thus they avoid the traditional load/store operations in the datapath that traditional CPUs perform. Such processing has the potential to provide orders of magnitude performance improvement, leading to further discoveries from vast amounts of data. The intellectual merit of this project emanates from the novel solutions needed: efficient FPGA designs to support region variables, time and counter constraints, region hierarchies, as well trajectory joins. If successful, this project has the potential to revolutionize the way queries over large trajectory data archives are processed. There is a broad range of applications (scientific, educational, and economic activities) that will be impacted from the fast processing provided by the FPGA filtering approach. Providing orders of magnitude speed improvement will have a profound effect in these applications. The combination of two distinct technologies (Databases and FPGAs) is an ideal vehicle for training graduate/undergraduate students and for transferring gained experience into relevant courses. For further information see the project web site at the URL: http://www.cs.ucr.edu/~tsotras/fpga/index.html

GPS和传感器技术的广泛采用创造了许多应用程序，这些应用程序以轨迹的形式收集和维护非常大的数据库。为了更好地分析这样的数据，用户可以使用高级的基于区域的表示来提出复杂的模式查询，该表示通过他们访问的空间区域（或感兴趣的区域/点）的时间排序序列来抽象轨迹。例如：“找到首先经过火车站，然后经过市中心，并且总是在离港口一英里范围内的移动物体”。可以添加时间和计数器约束，以及区域变量和区域层次结构，以创建非常强大的查询。类似地，人们可以制定连接查询，识别具有相似行为的轨迹对等。虽然这种基于模式的查询在分析大量轨迹档案中至关重要，但传统方法由于计算量大和数据大小而无法扩展。增加更多的资源（即，许多处理器）将不会消除瓶颈（每个处理器仍然在每个操作中使用多个时钟周期），并且还可能在处理器之间产生大的通信开销。相反，该项目采用了不同的，高风险高回报的方法，通过使用可重构硬件，即现场可编程门阵列（FPGA）。FPGA是代码加速器，其中应用程序的一部分被映射为FPGA上的电路;因此它们避免了传统CPU执行的数据路径中的传统加载/存储操作。这种处理有可能提供数量级的性能改进，从而从大量数据中获得进一步的发现。该项目的智力价值来自于所需的新颖解决方案：有效的FPGA设计，以支持区域变量，时间和计数器约束，区域层次结构以及轨迹连接。如果成功，该项目有可能彻底改变处理大型轨迹数据档案的查询方式。有广泛的应用（科学，教育和经济活动）将受到FPGA滤波方法提供的快速处理的影响。提供数量级的速度改进将在这些应用中产生深远的影响。两种不同技术（数据库和FPGA）的结合是培训研究生/本科生和将获得的经验转移到相关课程的理想工具。欲了解更多信息，请访问该项目网站的URL：http://www.cs.ucr.edu/~tsotras/fpga/index.html