以虛擬標記描述子之可擴展標記語言的路徑語言處理引擎

An XPATH Processing Engine for Virtual Token Descriptor

張維獻(Wei-Shian Chang)

指導教授 ： 王勝德

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2009年)

https://doi.org/10.6342/NTU.2009.00678

摘要

隨著可擴展標記語言(XML)被廣泛的使用在網際網路資訊交換中介軟體裡，其相關技術的研究也變的相當重要，可擴展標記語言是一種國際上通用的標準標記語言，它已變成用來表示各種資料來源的重要語言，也是為資料交換和資料儲存的一個中間語言，因此，電腦必須大量的來處理這些資料，導致於CPU的負載過重。
虛擬標記描述子(VTD)是種適合可擴展標記語言硬體實作的新方法。我們提出一種基於VTD資料結構的XPATH處理引擎架構，架構中分為前級的XPATH解析模組和後級的執行引擎模組。前級的XPATH解析模組主要在解析XPATH語法，此模組針對常用語法設計出多個小的有限狀態機模組平行處理，並有兩級管線設計，效能可達每秒處理114MBytes。後級的執行引擎模組主要在解碼前級的產生出來的操作碼，執行相對應的動作，比如說：搜尋VTD表格與找出正確VTD偏移量的機制。
本論文提出有關於以虛擬標記描述子之可擴展標記的路徑語言的硬體處理架構，它可以解析XPATH表示式產生出操作碼，然後它解碼和執行這些操作碼來得到搜尋的結果，在快速的搜尋擷取XML文件中的資訊，被提出的XPATH Processing Engine (XPE)效能可比軟體快達20倍以上。

關鍵字

XML XPATH VTD 硬體實作

並列摘要

XML (Extensible Markup Language) has been globally used as the most common. XML is a standard exchange format between diverse software because of its extensible characteristic. However, it is important and frequent that the content of XML document must be added, deleted, or navigated. XPATH is a language for finding information in an XML document. It describes location of specific XML element or attribute.
Virtual Token Descriptor (VTD) is a new technique of processing XML. We proposed an XPATH processing architecture that is based on a kind of data structure of VTD. In my architecture, the front stage is XPATH Parser module and back stage is Execution Engine module. There are many small parsing finite state machines (FSMs) for XPATH syntax in XPATH Parser module, these FSMs are parallel circuits and two stages pipeline design. XPATH Parser module performance can process 114Mbyes per second. The back stage is Execution Engine module, it executes operation codes that are from the front stage, searches VTD table, and finds correct VTD offsets method.
This thesis presents a hardware implementation of the VTD XPATH processor for XML language; it can parse the XPATH expression into operation codes, then it decode and execute these operation codes to get the resultant value. It is capable of retrieving information in an XML document in a speed of searching. The proposed XPATH Processing Engine (XPE) is 20 times faster than the software counterpart.

並列關鍵字

XML XPATH VTD Hardware implementation

參考文獻

[3] Hégaret, P. L., R. Whitmer, et al. (2005). "Document Object Model." from http://www.w3.org/dom/

[8] S. KUTTAPPA, "XPath Hardware Accelerator," North Carolina State University, 2007.

[1] "VTD-XML:The Future of XML Processing." from http://vtd-xml.sourceforge.net/.

[2] Clark, J. and S. DeRose (1999, 16 November). "XML Path Language (XPath)." 1.0. from http://www.w3.org/TR/1999/REC-xpath-19991116.

[4] "Simple API for XML." from http://www.saxproject.org.