CN105654383B - Low-delay FAST market decoding device and method based on pipeline architecture - Google Patents

Abstract

The invention relates to a low-delay FAST market decoding device and method based on pipeline architecture. The device includes an internal bus, a controller and field decoding operators for each field in the FAST market data, and each field decoding operator is connected to the internal bus respectively, and completes each field in the FAST market data sequentially under the control of the controller decoding; the internal bus is divided into a data bus and a control bus, and the data bus realizes the data transmission between the FAST market data input flow buffer and each field decoding operator and the FIX message buffer, and the control bus is responsible for controlling The decoding operation of each field. The field decoding operator is a three-segment decoding operator, and realizes pipelined FAST quotation decoding through a bus connection. The present invention can effectively accelerate the speed of market decoding, and provide support for financial applications such as algorithmic trading, high-frequency trading, and market risk monitoring.

Description

Low-latency FAST market decoding device and method based on pipeline architecture

technical field

The invention belongs to the field of information technology, and in particular relates to a low-latency FAST market decoding device and method based on a pipeline architecture.

Background technique

Financial exchanges release the latest market data to market participants in real time in the form of multicast. Market data includes the latest buying and selling quotations and demand, transaction records of financial products (such as opening price, highest price, lowest price, current price, transaction volume, transaction value, etc.), order status and other latest information. Financial participants analyze the incoming financial market data in real time through software such as market-watching software or algorithmic trading, and make financial transaction decisions (such as buying and selling financial products) based on the latest market conditions. Therefore, timely analysis of financial market data is crucial for market participants (especially algorithmic trading and high-frequency traders). Market participants who have obtained the latest market status can obtain instant market profits prior to other market participants.

Algorithm trading refers to the automatic realization of fast and low-cost order execution and transaction through computer programs. Specifically, it involves determining the best execution path, execution time, execution price and execution quantity of an order through a program. Algorithmic trading is widely used in pension funds, mutual funds, hedge funds, and other buy-side institutional investors. Through algorithmic trading, large transactions can be divided into many small transactions to cope with market risks and impacts, and at the same time provide liquidity for the market.

High Frequency Trading (High Frequency Trading, HFT) refers to a computerized transaction that uses a high-performance computing platform to seek price differences from extremely short-term market changes that people cannot take advantage of to achieve arbitrage. The response delay of high-frequency trading to market data is at the microsecond level, and each position is held for a very short time, and the position is basically closed at the close. High-frequency trading makes money by accumulating small profits that are frequent and numerous. High-frequency trading is widely used in market making, which provides liquidity to the market. High-frequency trading has accounted for 70% of the total turnover of the US stock market, 45% in Europe, and 40% in Japan. High-frequency trading has also begun to rise in emerging markets, if it is applied in domestic commodity futures, ETF or warrants, etc.

In the domestic financial market, financial information, including order data and market data, is mainly transmitted between trading institutions and market participants through the Securities Trading Exchange Protocol (STEP). STEP messages are fully compatible with the financial information exchange protocol (Financial Information Exchange, FIX) of foreign financial markets. A STEP/FIX message is strictly composed of multiple "tag=value" basic structures. This basic structure is called a domain or a field. Fields are separated by the field separator "SOH". Among them, "tag" is a field ID or field name, indicating a specific field, which implies information such as value type and value range, and "value" is the value of the field. For example, the field "270=342" indicates that the value of the field labeled 270 (representing "market item price" in STEP) is 342; SOH is a non-printable character, and its ASCII code is equal to 1.

In order to reduce market data transmission bandwidth requirements and transmission delay, the market publishing agency will choose the streaming FIX protocol (FIX Adapting for STreaming, FAST) to stream encode and compress the STEP/FIX market information. The FAST encoding method reduces the size of the data stream on two levels. First of all, the concept of "field operator" makes it possible to use the correlation of data in the stream and eliminate redundant data. Second, a self-describing field length (stop bit encoding mechanism) and a field presence bitmap (Presence Map, PMap) indicating the presence or absence of a field are utilized in the serialization of the remaining data in binary encoding. Coding is done according to control structures called "templates". A template controls the encoding of a portion of a stream by specifying the order and structure of the fields, field operators, and the binary-encoded representation they use. For more specific details, please refer to the FIX/STEP and FAST protocol specification documents. For the convenience of description, the present invention refers to the binary data obtained after each field of FIX/STEP is encoded by FAST as the encoded value of the field.

With the increasingly open development of China's financial market, financial applications such as high-frequency trading and algorithmic trading will surely occupy a larger market share in China's financial market in the future. Timely analysis of financial market data is a prerequisite for financial applications such as algorithmic trading, high-frequency trading, and financial risk monitoring. With increasingly fierce competition in the financial market, financial risks have a greater impact on institutions themselves, the entire financial market, and even society than before. Therefore, there is an urgent need to study a low-latency FAST market decoding technology to support financial risk monitoring, algorithmic trading, and other application requirements that require low-latency market processing. At the same time, it can also promote the liquidity of financial markets.

The current FAST market decoding is mainly based on software methods, such as using open source market software OpenFAST (sourceforge.net/projects/openfast/), QuickFAST (www.ociweb.com/products/quickfast/), or the company's own market development decoding system. Software-based decoding methods introduce additional data processing delays. On the one hand, the software network protocol stack delay introduced by market network packet analysis: two memory copy delays and waiting for system interrupt processing delay; on the other hand, the system jitter delay introduced by the operating system, including multi-process competition for system resources , interrupt wait, etc. Usually, the market processing delay of the software is at the millisecond level. Millisecond-level market decoding delay is difficult to meet real-time applications such as high-frequency trading and market risk monitoring.

On the other hand, FAST messages have strong data dependencies. The encoded FAST market information is a binary data stream, and the fields and messages are sequentially identified through the PMap and stop bit encoding mechanism. That is, the position of the next field in the input market stream can be determined only after reading the FAST encoded value of a field from the input stream; similarly, only after reading a FAST message can the next FAST message be read from the input stream. The data dependency of FAST messages limits parallel decoding of FAST quotes. The published literature has not yet realized the work of parallel decoding of FAST market information.

Contents of the invention

The purpose of the present invention is to provide a device and method for accelerating the decoding of FAST market data based on dedicated hardware, which can effectively accelerate the speed of market decoding and provide support for financial applications such as algorithmic trading, high-frequency trading, and market risk monitoring.

The technical scheme that the present invention adopts is as follows:

A low-latency FAST quotation decoding device based on a pipeline architecture, comprising an internal bus, a controller, and field decoding operators for each field in the FAST quotation data, each field decoding operator is connected to the internal bus respectively, and in the control The decoding of each field in the FAST market data is completed sequentially under the control of the device; the internal bus is divided into a data bus and a control bus, and the data bus realizes the FAST market data input stream buffer and each field decoding operator and FIX message buffer The data transmission between, the control bus is responsible for controlling the decoding operation of each field.

Further, the field decoding operator is a three-segment decoding operator, and is connected through a bus to realize pipelined FAST quotation decoding; the three-segment decoding operator includes three steps of reading data, field decoding, and decoding result output. The intermediate results are cached through the cache between the three components. Among them, the reading data part is responsible for reading the encoded value of the field from the FAST market data input stream buffer, the field decoding part is responsible for specific decoding according to the rules of the field operator, and the result output part is responsible for outputting the decoded field value to the output FIX message buffer device. The pipelined FAST market decoding includes three independent pipelines: the read data parts of all field decoding operators are respectively connected to the internal bus, and are connected with the read controller to form a read data pipeline; the decoding parts of all field decoding operators are respectively It is connected to another internal bus and connected to the decoding controller to form a decoding pipeline; the result output components of all field decoding operators are respectively connected to another internal bus and connected to the output controller to form an output pipeline.

Further, the controller is realized by a finite state machine mechanism with a data path, and the inside of the controller is divided into a control path and a data path, and both paths are internally implemented by a finite state machine; the control path is a top-level field Decoding task scheduler, which sequentially sends instructions for each field decoding operator to start the decoding operation; the data path contains the specific control logic of each decoding operator; when the decoding operator of a field completes decoding, the data path goes to the control layer Returns the decoding end signal.

A low-latency FAST quotation decoding method based on a pipeline architecture using the above-mentioned device, the field decoding operator is divided into three parts: reading data, field decoding, and decoding result output, and realizing pipelined FAST quotation decoding through bus connection, Including the following steps:

1) The read data parts of all field decoding operators are respectively connected to the internal bus, and are connected with the read controller to form a read data pipeline; the encoded value of the field is read from the FAST market data input stream buffer through the read data part;

2) The decoding components of all field decoding operators are respectively connected to another internal bus and connected to the decoding controller to form a decoding pipeline; the field decoding components are responsible for specific decoding according to the rules of field operators;

3) The result output parts of all field decoding operators are respectively connected to another internal bus and connected to the output controller to form an output pipeline; the result output part is responsible for outputting the decoded field values to the output FIX message buffer.

Utilize device and method provided by the present invention to process FAST market data decoding, have the following advantages:

1. Obtain FAST market data processing speed with extremely low latency. The delay in decoding a FAST quote is at the level of 0.1 to 1 microsecond. Realize FAST market decoding based on dedicated hardware, which can avoid the additional processing delay introduced by the software system.

2. The FAST market data decoding processor based on the bus architecture has good scalability and supports flexible field updates. To add a new operator, you only need to mount the operator to the bus, and to delete an operator, you only need to unload the operator from the bus. This is important for financial applications, because FAST market templates may be updated frequently.

3. The pipeline-based FAST market decoding processor solves the difficulty of relying on FAST market data, solves the difficulty that FAST market data cannot be decoded in parallel, and realizes parallel decoding between multiple fields and multiple messages; and the connection between each stage of the pipeline The reasonable representation of intermediate results generally adopts the representation method of "value existence mark + value". Compared with the FAST market processor that does not use the pipeline architecture, theoretically, the performance can be accelerated by 3 times; the actual measurement results show that the performance has increased by 1.8 times.

4. The controller is implemented based on a finite state machine with a data path, which simplifies the control and update logic.

5. The present invention is applicable to a differential decoding protocol whose task is similar to that of the FAST protocol structure.

The actual measurement environment of the above points 1 and 3 is: the FPGA chip is: Xilinx Zynq-7000chip (XC7Z020-3CLG484); a FAST template contains 12 fields.

Description of drawings

Figure 1 is a schematic diagram of the FAST market decoding processor based on the bus architecture.

Fig. 2 is a schematic diagram of a field decoder of a three-stage pipeline.

Fig. 3 is a schematic diagram of a FAST market decoding processor with a three-stage pipeline.

Figure 4 is a schematic diagram of the controller based on FSMD.

Fig. 5 is a schematic diagram of a FAST quotation message decoding processor implemented based on FPGA.

Detailed ways

In order to make the above objects, features and advantages of the present invention more obvious and understandable, the present invention will be further described below through specific embodiments and accompanying drawings.

In the present invention, special hardware is used to accelerate the decoding of FAST market data, such as FPGA (Field Programmable Gate Array, Field Programmable Gate Array), ASIC (Application Specific Integrated Circuit, application specific integrated circuit) and the like.

First of all, the FAST market decoding processor based on the bus architecture is designed. For a specific FAST market template, first connect the decoders (also called decoding operators) of each field defined in the template to the internal bus of the decoding processor. The internal bus is divided into two types: data bus and control bus. Under the control of the decoding controller, the decoding of each field is completed in turn.

After that, optimize and improve the FAST market decoding processor with bus architecture, and design a three-stage pipelined FAST market decoding processor. Through ingenious pipeline design, it realizes serial reading of data between FAST fields and FAST messages, parallel decoding, and serial output of decoded data. Greatly improved the speed of FAST market decoding. Each field decoding operator of the pipeline-based FAST market decoding processor is designed as a three-stage decoding operator, and then each decoding operator is connected through a bus to realize a pipelined overall FAST market decoder.

1. FAST market decoding processor based on bus architecture

First, design and implement all field operators supported by the FAST protocol, and implement these operators as a decoding operator library. For the decoding of a specific FAST template, first instantiate each field from the decoding operator library according to each field defined in the template. Figure 1 describes the FAST market decoding processor based on the bus architecture. Each instantiated field decoder is separately connected to the internal bus of the decoding processor. The internal bus is divided into two types: data bus and control bus. The data bus realizes the data transfer between the FAST market data input stream buffer (FAST-MSG FIFO) and each field decoder, and the FIX message buffer (FIX-MSG FIFO); the control bus is responsible for controlling the decoding operation of each field. When the FAST market data input stream buffer is not empty, the controller first activates the PMap field decoder (PMap Decoder) to read the encoded value of the PMap field from the input stream to obtain the PMap vector. Then start the decoding of the template ID (TID Decoder in the figure). Thereafter, the decoding operations of the subsequent fields are sequentially activated (fld ₁ Decoder to fld _n Decoder in the figure). The decoding of the next field can only be started after the decoding of the previous field is completed. Since the FAST message is data-dependent, the decoding of each field needs to judge whether there is a field value in the input data stream according to the PMap bit of the field. The FAST quotation decoding processor based on the bus structure proposed by the present invention has good expansibility. To add a new field, you only need to mount the new decoding operator to the bus and modify the control logic of the controller; to delete a field, you only need to unload the decoding operator from the bus and modify the control logic of the controller. Can. Scalability is especially important for financial applications that require frequent updates.

2. FAST market decoding processor based on pipeline

Figure 2 describes the field decoding operator of the three-stage pipeline architecture. The field decoding operator is divided into three parts: reading data (reader), field decoding (decoder), and decoding result output (writer). The intermediate results are cached between the three components through a buffer (FIFO). The read data component is responsible for reading the encoded value of the field from the input stream (FAST-MSG FIFO); the field decoding component is responsible for specific decoding according to the rules of the field operator; the result output component is responsible for outputting the decoded field value to the output FIX message buffer (FIX-MSG FIFO).

Figure 3 describes the architecture of the parallel FAST market decoding processor. The processor is divided into three independent pipelines. Each field is a three-segment field decoding operator, which is divided into three major parts: reading data, field decoding, and decoding result output. The data reading components of all (field) decoding operators are respectively connected to the internal bus (internal is divided into data bus and control bus), and connected to the reading controller (reading control, RC) to form the reading data pipeline of the FAST market processor. The read controller controls the specific read operation of each decoding operator. Similarly, the decoding components of all decoding operators are respectively connected to another internal bus, and connected to the decoding controller (decoding control, DC) to form the decoding pipeline of the FAST market processor; the result output components of all decoding operators are respectively connected to another An internal bus is connected with the output controller (writingcontrol, WC) to form the output pipeline of the FAST market processor. The working mechanism of each pipeline is described in detail below.

a) Read data pipeline:

The reading components of each field are activated sequentially to realize the sequential reading of the coded values of the fields. When the input FAST message buffer (FAST-MSG FIFO) is not empty, the read data controller RC sends a read data start signal to the read data component (PMap reader) of the PMap decoding operator. After the component reads the data, it activates its subsequent component (template ID field, tid reader) to read the data. By analogy, the read controller sequentially activates the read data components of subsequent fields according to the PMap state and the field order defined by the FAST template. When the last field has finished reading data, notify RC that a FAST message has been read. At this time, if the buffer of the input FAST data stream is not empty, the RC restarts the reading work of a new FAST message; otherwise, it enters an idle waiting state.

The reading part of each operator writes the coded value read in into the field coded value buffer xxx_in_fifo (the "xxx" characters appearing in the present invention represent the specific field name in the figure, such as the first field in the FAST template The encoded value buffer is "fld1_in_fifo", see Figure 3), and the basic storage unit format of this buffer is: "[pmap_bit][value]". pmap_bit is the PMap flag bit of the field, and the field decoding component needs to use this flag to decide how to encode. That is, the decoder needs to know that the current field has no encoded value in the input stream, and whether it needs to use the previous value or the initial value to restore the field value, such as when the PMap flag of the copy (COPY) operator field is 0.

b) Decoding pipeline

The decoding part of each field performs decoding in parallel. Reading the coded value of a field from the field coded value buffer may not need to read the coded value of the field, which is determined by the rules of the field operator and the state of the field PMap. Field decoding is then performed according to the rules for field operators. Finally, output the decoding result to the field value buffer (xxx_out_fifo).

The basic storage unit structure of the field value buffer (xxx_out_fifo) is: "presence_flag[value]". When this field has a value, presence_flag=1; when this field has no value, presence_flag=0, and "value" is empty. When the current field of the message is empty, the field output component needs to know that the field has no value, it does not need to write any data to the output buffer. "value" is the field value. Variable-length string field values end with '\0'.

c) Output pipeline

The activation mechanism of the output pipeline is the same as that of the read data pipeline, and the output components (xxx_writer) of each field are activated sequentially. After each output unit receives the output data start signal from the output controller, it reads the field value in the corresponding field value buffer (xxx_out_fifo). If the read field code value presence flag (presence_flag) is 0, it means no If the field value needs to be output, then end the output work of this field; otherwise, read a field value from the field value buffer, and then write it into the FIX message buffer (FIX-MSG FIFO) byte by byte. After the output ends, the output controller notifies the subsequent output components to continue outputting field values.

3. Controller

The controller in the present invention is realized by a finite state machine (Finite State Machine with Datapath, FSMD) mechanism with a data path, as shown in FIG. 4 . The inside of the controller is divided into a control path and a data path, both of which are implemented by a finite state machine (FSM). The control path is a top-level field decoding task scheduler, which sequentially sends instructions (xxx_dec_begin) for each field decoding operator to start the decoding operation; the data path contains the specific control logic of each decoding operator. When the decoding operator of a field completes the decoding, the data channel will return the decoding end signal (xxx_dec_done) to the control layer.

4. FPGA-based low-latency market decoding processor

The quotation decoding framework proposed by the present invention can be realized on special hardware such as FPGA (Field Programmable Gate Array), ASIC (Application Specific Integrated Circuit) and the like. This section takes the FPGA platform as a column and gives a specific implementation.

Figure 5 shows the frame diagram of the FAST market information decoding processor based on FPGA. Wherein, the financial quotation processor is the pipeline-based FAST quotation decoding processor proposed by the present invention. There is a data exchange module inside the FPGA chip, which is responsible for the fast data exchange between the market processor and the external system. On the one hand, the data exchange module is responsible for receiving the real-time market data stream released from the exchange, unpacking and further analyzing the received data packets and extracting the FAST market data, and buffering them in the FAST market data buffer (FAST-MSG-FIFO ). On the other hand, the data exchange module is responsible for transmitting the decoded FIX message to the financial application system (including necessary packets). Since the exchange releases the market in real time through multicast, the data exchange module accesses the market data through a high-speed network interface, such as through 10/40G PYH+QSFP++GMAC core, etc.; the decoded FIX market information is transmitted to the financial application system It can be a high-speed network interface, or it can realize the rapid transmission of market prices through PCIExpress interface + DMA communication.

The above embodiments are only used to illustrate the technical solution of the present invention and not to limit it. Those of ordinary skill in the art can modify or equivalently replace the technical solution of the present invention without departing from the spirit and scope of the present invention. The scope of protection should be determined by the claims.

Claims (9)

1. A low-delay FAST market decoding device based on a pipeline architecture is characterized by comprising an internal bus, a controller and field decoding operators of fields in FAST market data, wherein the field decoding operators are respectively connected to the internal bus, and the decoding of the fields in the FAST market data is sequentially completed under the control of the controller; the internal bus is divided into a data bus and a control bus, the data bus realizes data transmission among a FAST market data input stream buffer, each field decoding operator and a FIX message buffer, and the control bus is responsible for controlling the decoding operation of each field;

The field decoding operator is a three-section decoding operator and realizes the pipeline FAST market decoding through bus connection; the three-section decoding operator comprises three components of reading data, decoding a field and outputting a decoding result, and intermediate result caching is carried out among the three components through a cache; the field decoding component is responsible for specific decoding according to rules of field operators, and the result output component is responsible for outputting decoded field values to the FIX message buffer; the pipelined FAST market decoding comprises three independent pipelines: the data reading components of all the field decoding operators are respectively connected to the internal bus and connected with the data reading controller to form a data reading pipeline; the decoding components of all the field decoding operators are respectively connected to the other internal bus and connected with a decoding controller to form a decoding pipeline; the result output parts of all the field decoding operators are respectively connected to the other internal bus and connected with the output controller to form an output pipeline;

Through the three independent pipelines, serial data reading, parallel decoding and serial data output decoding between FAST fields and FAST messages are realized, and the method comprises the following steps:

The data reading assembly line sequentially activates data reading components of decoding operators of all the fields to realize sequential reading of the coded values of the fields;

In the decoding pipeline, a field decoding component of each field decoding operator reads the coded value of a field from a field coded value buffer, performs field decoding in parallel according to the rule of a field operator, and finally outputs a decoding result to a field value buffer;

The activation mechanism of the output pipeline is the same as that of a read data pipeline, the output components of all fields are sequentially activated, and after each output component receives an output data starting signal sent by the output controller, the field value in the corresponding field value buffer is read and written into the FIX message buffer byte by byte.

2. The apparatus of claim 1, wherein: the controller is realized by adopting a finite state machine mechanism with a data path, the controller is internally divided into a control path and a data path, and the interiors of the two paths are realized by the finite state machine; the control path is a field decoding task scheduler at the top layer, and the control path sequentially sends out instructions for starting decoding operation of each field decoding operator; the data path comprises specific control logic of each decoding operator; and when the decoding operator of one field completes decoding, the data path returns a decoding end signal to the control layer.

3. The apparatus of claim 1, wherein: the method is realized on special hardware, and the special hardware is FPGA or ASIC.

4. The apparatus of claim 3, wherein: the method is realized on an FPGA chip, a data exchange module in the FPGA chip is responsible for FAST data exchange with the outside, on one hand, the data exchange module is responsible for receiving real-time market data flow issued from a trading exchange, unpacking and further analyzing the received data packet, extracting FAST market data and caching the FAST market data into a FAST market data cache; on the other hand, the data exchange module is responsible for transmitting the decoded FIX message to the financial application system.

5. A low-latency FAST market decoding method based on a pipeline architecture and adopting the device of claim 1, wherein a field decoding operator is divided into three components of reading data, field decoding and decoding result output, and the pipelined FAST market decoding is realized through bus connection, comprising the following steps:

1) The data reading components of all the field decoding operators are respectively connected to the internal bus and connected with the data reading controller to form a data reading pipeline; reading the coded value of the field from the FAST market data input stream buffer by a data reading component; the data reading assembly line sequentially activates data reading components of decoding operators of all the fields to realize sequential reading of the coded values of the fields;

2) The decoding components of all the field decoding operators are respectively connected to the other internal bus and connected with a decoding controller to form a decoding pipeline; the field decoding component is responsible for specific decoding according to the rules of the field operator; in the decoding pipeline, a field decoding component of each field decoding operator reads the coded value of a field from a field coded value buffer, performs field decoding in parallel according to the rule of a field operator, and finally outputs a decoding result to a field value buffer;

3) The result output parts of all the field decoding operators are respectively connected to the other internal bus and connected with the output controller to form an output pipeline; outputting the decoded field value to a FIX message buffer through a result output component; the activation mechanism of the output pipeline is the same as that of a read data pipeline, the output components of all fields are sequentially activated, and after each output component receives an output data starting signal sent by the output controller, the field value in the corresponding field value buffer is read and written into the FIX message buffer byte by byte.

6. The method of claim 5, wherein: when the input stream buffer of the FAST market data is not empty, the read controller sends a read data starting signal to a read data component of the PMap decoding operator, the read data component activates the subsequent component to read the data after reading the data, and so on, the read controller activates the read data component of the subsequent field in sequence according to the PMap state and the field sequence defined by the FAST template; when the last field finishes reading data, the reading controller is informed that a FAST message is completely read, at this time, if the input FAST data stream buffer is not empty, the reading controller restarts the reading work of a new FAST message, otherwise, the reading controller enters an idle waiting state.

7. The method of claim 6, wherein: and the read data component of each field decoding operator writes the read-in coded value into a field coded value buffer, and the basic storage unit format of the field coded value buffer is [ PMap _ bit ] [ value ], wherein PMap _ bit is the PMap flag bit of a field, and value is the value of the flag bit.

8. The method of claim 7, wherein: the basic storage unit structure of the field value buffer is a presence _ flag [ value ], and when the field has a value, the presence _ flag is 1, and when the field has no value, the presence _ flag is 0.

9. The method of claim 8, wherein: if the field value read by each output component has a flag presence _ flag of 0, which indicates that no field value needs to be output, the field output operation is ended; otherwise, reading a field value from the field value buffer, writing the field value into the FIX message buffer byte by byte, and after the output is finished, the output controller informs the subsequent output component to continue outputting the field value.