JP2023164403A - Method and system for reducing data stored in capture buffer - Google Patents

Abstract

To provide a method and system for reducing data stored in a capture buffer of an interposer circuit during communication of the data over a data link according to a high-speed, layered packet-based protocol for analysis.SOLUTION: The method includes: performing data integrity checks of the data in real time, and omitting data integrity bits corresponding to the data integrity checks from transaction layer packets (TLPs) and data link layer packets (DLLPs) of the data when the data is correct; performing ACK/NACK matching in real time to confirm successful delivery of the TLPs of the data using ACK/NACK packets, where the ACK/NACK packets are omitted from being stored in the capture buffer; removing and/or reducing fields in real time from the TLPs and/or the DLLPs of the data; and compressing data payloads of the TLPs and/or the DLLPs of the data in parallel.SELECTED DRAWING: Figure 2

Description

[Cross reference to related applications]
This application is filed under 35 U.S.C. 119(e) in U.S. Provisional Application No. 63/336,009, filed on April 28, 2022; Application No. 63/399,118, U.S. Provisional Application No. 63/418,761 filed October 24, 2022, and U.S. Provisional Application No. 63/431,100 filed December 8, 2022. No. 18/090,311, filed December 28, 2022, which claims priority to US Pat. The entire disclosures of U.S. Provisional Application No. 63/336,009, U.S. Provisional Application No. 63/399,118, U.S. Provisional Application No. 63/418,761, and U.S. Provisional Application No. 63/431,100 are incorporated herein by reference. The entirety of this document is hereby specifically incorporated by reference.

Peripheral Component Interconnect Express (PCIe) is a system that connects a personal computer's host central processing unit (CPU) to a computer, such as a graphics card, sound card, or solid-state drive (SSD). (solid state drives) and various high-speed peripheral components such as workload accelerator cards used in data centers. Therefore, after the latest version of the specification is developed, new products based on the PCIe interconnect must be launched quickly in order to capture as much of the market as possible. To reduce time to market, we use a variety of tools to support and accelerate development activities. One commonly used tool is a PCIe protocol analyzer. Conventional PCIe protocol analyzers support various display and protocol search functions intended to assist the user in detailed analysis and debugging of the PCIe interactions between the various modules communicating on the PCIe bus.

In general, PCIe is a layered packet-based protocol used as a high-speed hardware interface for connecting peripheral devices, and in this protocol, data is mainly transferred in the upper two layers called the data link layer and the transaction layer. be done. The data link layer supports guaranteed delivery with acknowledgments, flow control, and power management functions. Above the data link layer, the transaction layer implements split transactions (transactions where the request and response are separated by time) so that while the target device collects data for the response, the communication link collects data for other traffic. be able to be transported. The lowest layer of a hierarchical packet-based protocol is called the physical layer.

The latest version of PCIe in the development stage, the PCIe Gen6 protocol by the Peripheral Component Interconnect Special Interest Group (PCI-SIG(TM)), supports 64 GB/s for the PCIe Gen5 protocol and 32 GB for the PCIe Gen4 protocol. It is contemplated that the multi-lane bandwidth will increase from the traditional multi-lane bandwidth of 128 GB/sec to up to 128 GB/sec. By supporting very high throughput, the PCIe Gen6 protocol is widely used in the storage industry for Non-Volatile Memory Express (NVMe), Serial Advanced Technology Attachment (SATA), and small computer systems. In addition to being used in conjunction with the Small Computer System Interface (SCSI) express protocol, it is also expected to be used in future accelerator protocols such as CXL, CCIX, and Gen-Z. To accommodate such high bit rates, when PCIe protocol analyzers capture protocol exchanges on the PCIe bus, solutions proposed so far rely on large memory buffers for storage, e.g. It can support full 64GB/s data capture for up to 4 seconds on Gen5.

However, such approaches are costly due to the large amount of data that needs to be transferred, stored, and ultimately processed, and are also error-prone, resulting in poor signal integrity. , and can lead to data processing challenges.

The exemplary embodiments are best understood from the following detailed description when read in conjunction with the accompanying drawings. It is emphasized that the various features are not necessarily drawn to scale. In practice, the dimensions may be arbitrarily enlarged or reduced for clarity of discussion. Wherever applicable and practical, like reference numbers refer to like elements.

A simplified block diagram of a system that reduces the amount of data stored during the capture of data communications over high-speed data links without loss of functionality and without loss of information available for analysis, according to exemplary embodiments. It is a diagram. Capture buffers of interposer circuits without loss of functionality and without loss of information available for analysis during communication of data over a data link that conforms to a high-speed hierarchical packet-based protocol, according to exemplary embodiments. 2 is a simplified flowchart illustrating a method for reducing the amount of data stored in a computer. CRC fields of an example transaction layer packet (TLP) and an example data link layer packet (DLLP) to be discarded without being stored in a capture buffer, according to a representative embodiment. FIG. FIG. 4 illustrates TLP and DLLP sequence number fields that allow ACK/NACK packets to be discarded without being stored in a capture buffer, according to an exemplary embodiment. FIG. 4 illustrates framing token fields of TLPs and DLLPs that should be discarded rather than stored in a capture buffer, according to an exemplary embodiment. FIG. 2 illustrates FLIT of an exemplary 16-lane Gen6 PCIe link. FIG. 4 illustrates known fields of an example configuration read TLP to be discarded rather than stored in a capture buffer, according to a representative embodiment. FIG. 6 is a diagram illustrating reducible fields of a configuration read TLP to be reduced in size before being stored in a capture buffer, according to an exemplary embodiment; FIG. 3 is a diagram illustrating an example of wideword data symbols configured to enable parallel data compression in a single circuit, according to a representative embodiment. 4 illustrates a method for performing parallel data compression of a data payload to be stored in a capture buffer of an interposer circuit during communication of data over a data link that conforms to a high speed layered packet-based protocol, according to a representative embodiment; This is a simplified flowchart. 1 is a diagram illustrating symbols of wideword data input for decompression with conventional decompression techniques; FIG. FIG. 4 illustrates symbols of wideword data reordered for input for decompression, according to an exemplary embodiment. FIG. 7 illustrates another example of reordering symbols of wideword data input for decompression, in accordance with representative embodiments. FIG. 7 illustrates another example of reordering symbols of wideword data input for decompression, in accordance with representative embodiments. 3 is a flowchart illustrating a method of creating an inverse structure for decompression, according to an exemplary embodiment. FIG. 3 illustrates parallel compression of wideword data to reorder symbols of wideword data input for decompression, according to an exemplary embodiment. FIG. 3 is a diagram illustrating reordering symbols of a wideword data input for decompression, according to an exemplary embodiment. FIG. 3 illustrates decompression of permuted symbols of wideword data in accordance with a representative embodiment. FIG. 3 illustrates symbols of wideword data shifted for input for decompression, according to an exemplary embodiment. FIG. 3 illustrates parallel compression of wideword data for shifting symbols of wideword data input for decompression, according to an exemplary embodiment. FIG. 3 is a diagram illustrating shifting symbols of a wideword data input for decompression, according to an exemplary embodiment. FIG. 3 illustrates decompression of shifted symbols of wideword data in accordance with an exemplary embodiment. 2 is a simplified flowchart illustrating a method of providing decompressed wideword data during communication of wideword data over a data link, according to an exemplary embodiment. 2 is a simplified flowchart illustrating a method of providing decompressed wideword data during communication of wideword data over a data link, according to an exemplary embodiment. 1 is a simplified block diagram illustrating an example of a computer system that reduces the amount of data stored during communication of data over a high speed data link, according to a representative embodiment. FIG. 1 is a simplified block diagram illustrating an example of a computer system that reduces the amount of data stored during communication of data over a high speed data link, according to a representative embodiment. FIG. The left side is an output after compression from non-random data, while the right side is a diagram showing an example of an output after compression from random data. FIG. 3 is a diagram illustrating an example of symbols of wide word data configured for parallel data compression with excellent compression efficiency, according to a representative embodiment. 2 is a flowchart of a method for improving compression of wide word data in real time, according to an exemplary embodiment.

The following detailed description sets forth representative embodiments that disclose specific details for purposes of explanation, and not limitation, to provide a thorough understanding of an embodiment according to the present teachings. . Descriptions of known systems, devices, materials, methods of operation, and methods of manufacture may be omitted to avoid obscuring the description of the representative embodiments. Nevertheless, systems, devices, materials and methods within the understanding of those skilled in the art are within the scope of the present teachings and may be used in accordance with the exemplary embodiments. It is to be understood that the terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting. Defined terms have meanings as commonly understood and accepted in the art to which the present teachings apply, in addition to their scientific and technical meanings.
Although terms such as first, second, third, etc. may be used herein to describe various elements or components, these elements or components are also referred to by these terms. It should be understood that it should not be limited. These terms are only used to distinguish one element or component from another. Accordingly, a first element or component discussed below may be referred to as a second element or component without departing from the teachings of this disclosure.

The terminology used herein is for the purpose of describing particular embodiments only and is not intended to be limiting. As used in this specification and the appended claims, the singular terms "a," "an," "the," and "the" are clearly defined as having other meanings depending on the context. is intended to include both singular and plural forms, except where indicated. Additionally, the term "comprises, comprising" and/or similar terms (i.e., the term "comprises, including" and/or similar terms) as used herein , specifies the presence of the mentioned feature, element and/or component, but does not exclude the presence or addition of one or more other features, elements, components and/or groups thereof. As used herein, the term "and/or" includes any and all combinations of one or more of the associated listed items.

Unless otherwise stated, an element or component is "connected to" or "coupled to" or "adjacent to" another element or component. It is to be understood that when referred to as, the element or component may be directly connected or coupled to other elements or components, or there may be intervening elements or components. That is, these terms and similar terms include instances where one or more intermediate elements or components may be utilized to connect two elements or components. However, when an element or component is said to be "directly connected" to another element or component, this does not mean that the two elements or components are connected to any intermediate or intervening elements or components. Contains only cases that are connected to each other without using any elements.

The present disclosure, through one or more of its various aspects, embodiments and/or specific features or subcomponents, therefore provides one or more of the advantages as specifically mentioned below. is intended to clarify. For purposes of explanation, and not limitation, exemplary embodiments are described that disclose specific details to provide a thorough understanding of an embodiment according to the present teachings. However, other embodiments that depart from the specific details disclosed herein but are consistent with this disclosure are still within the scope of the following claims. Moreover, descriptions of well-known devices and methods may be omitted so as not to obscure the description of the example embodiments. Such methods and apparatus are within the scope of this disclosure.

According to exemplary embodiments, during communication of data over a data link that conforms to a high-speed layered packet-based protocol between a system under test and a protocol analyzer for analysis, without loss of functionality and analysis. A method is provided to reduce the amount of data stored in the capture buffer of an interposer circuit without losing information available in the interposer circuit. This method performs a data integrity check of the data in real time, and if the data integrity check indicates that the data is correct, the data is transferred to a transaction layer packet (TLP) and a data link. Omitting the data integrity bits corresponding to data integrity checks from the data link layer packet (DLLP) from being stored in the capture buffer and using ACK/NACK packets to ensure that the TLP of the data is correct. In order to confirm that the packet has been delivered to the capture buffer, we perform real-time verification of the acknowledgment and negative response (ACK/NACK), and omit this ACK/NACK packet from being stored in the capture buffer. deleting and/or reducing fields (i.e., deleting and/or reducing) in real time from a TLP and/or DLLP (i.e., TLP and/or DLLP) of data to be stored; and/or or compressing the TLP and/or DLLP payload of the data to be stored in the capture buffer in parallel.

According to an exemplary embodiment, the system transmits data in a high-speed layered packet-based protocol from a device under test (DUT) to a host computer via a high-speed data link that conforms to a high-speed layered packet-based protocol. A user interface (UI) computer configured to run analyzer software for analysis and an interposer circuit connected to a high-speed data link to monitor data transmitted between the DUT and the host computer. The interposer circuit includes a capture buffer for storing data transmitted between the DUT and the host computer, and the interposer circuit can be accessed by the UI computer for analysis with analyzer software. include. The interposer circuit performs a data integrity check of the data in real time, and if the data integrity check indicates that the data is correct, it responds to data integrity checks from the TLP and DLLP of the data. By omitting data integrity bits from being stored in the capture buffer and using ACK/NACK packets, ACK/NACK verification is performed in real time to ensure that the data's TLP is successfully delivered. executing and omitting this ACK/NACK packet from being stored in the capture buffer; and removing and/or reducing fields in real time from the TLP and/or DLLP of data to be stored in the capture buffer; and/or compressing the TLP and/or DLLP payload of data to be stored in the capture buffer in parallel.

According to an exemplary embodiment, the system executes analyzer software that analyzes data from the DUT to the host computer via a high-speed data link that conforms to a high-speed hierarchical packet-based protocol. an interposer circuit connected to the high-speed data link for monitoring data transmitted between the DUT and the host computer, the interposer circuit configured to communicate with the DUT and the host computer; and an interposer circuit that the UI computer can access for analysis with analyzer software. The interposer circuit is programmed to compress TLPs and/or DLLPs in parallel and store the compressed TLPs and/or DLLPs in a capture buffer, each of which includes a header and a payload. Compressing a TLP and/or DLLP involves receiving TLP and/or DLLP symbols on multiple serial high-speed lanes at an interposer circuit and combining the symbols from the serial high-speed lanes with the TLP and/or DLLP clock. deskewing into widewords that arrive at each clock of the cycle; and arranging the widewords into input streams, each input stream containing the output from the same position of each wideword that arrives at each clock of the clock cycle. compressing the symbols using a hash table for compressing the symbols, and finally storing the compressed symbols in a capture buffer.

According to an exemplary embodiment, a method is provided for decompressing parallel compressed wideword data. The method is to create an instance of a wideword memory structure in wideword data, where the above instance of the memory structure is an instance of the inverse of a wideword compression dictionary. and using said instance of a memory structure to iteratively obtain a plurality of compressed symbols from a gap-free compressed output stream of wideword data, said plurality of Each compressed code of the compressed codes includes at least one character code and a reverse pointer, and each compressed code of the plurality of compressed codes includes at least one character code and a reverse pointer. includes a multi-symbol string having a plurality of character codes; repeatedly following each inverse pointer that is a plurality of compressed codes to form a decompressed intermediate stream; and at least one compressed reversing the order of the multiple character codes of the multi-symbol string of the subsequent code to form a decompressed stream.

FIG. 1 illustrates a system for reducing the amount of data stored during communication of data over a high-speed data link without loss of functionality and without loss of information available for analysis, according to an exemplary embodiment. FIG. 2 is a simplified block diagram.

Referring to FIG. 1, system 100 includes a user interface (UI) computer 110 and an interposer circuit 120. The interposer circuit 120 is configured to connect a device under test (DUT) 140 and a host computer 150 of the system under test over a high speed data link 130 and to receive and process data communicated over the high speed data link 130. Ru. Data is provided by interposer circuit 120 to UI computer 110, which hosts a protocol analyzer for analyzing the data according to high speed data protocols.

Thus, interposer circuit 120 serves as a "man in the middle" for testing a system under test that includes DUT 140, host computer 150, and high-speed data link 130 between DUT 140 and host computer 150. Function. That is, interposer circuit 120 captures high-speed data during testing and stores a portion of the captured data in capture buffer 125, in accordance with embodiments described herein, and this data is used for post-capture analysis. UI computer 110. Interposer circuit 120 may be connected to UI computer 110 with, for example, a universal serial bus (USB) (eg, USB 3.0) or Ethernet connection.

UI computer 110 may be, for example, a personal computer (PC), but may also incorporate any processing unit capable of running a protocol analyzer (e.g., processing unit 810, described below) without departing from the scope of the present teachings. . Similarly, host computer 150 may be, for example, a PC, but may include any processing unit (e.g., processing unit 810 described below) that can interface with DUT 140 via a high-speed data protocol without departing from the scope of the present teachings. , can also be incorporated. For example, DUT 140 may be a high-speed peripheral device, such as an add-in card or a system board, that is insertable into and interfaces with host computer 150. Examples of high speed peripheral devices include graphics cards, sound cards, SSDs, and workload accelerators. In general, high-speed peripheral devices are those that operate at data rates greater than 0.25 GB/s per lane, depending on the specification (e.g., greater than 4 GB/s per lane in the PCIe Gen6 protocol); , data needs to be communicated with high speed protocols over high speed data link 130 for reliable data transfer.

High-speed data protocols include, for example, PCI Express™ Base Specification Revision 3.0 (November 10, 2010) (“PCIe Gen3 Protocol”), PCI Express™ Base Specification Revision 4.0, Version 1.0 (October 5, 2017) ("PCIe Gen4 Protocol"), PCI Express(TM) Base Specification Revision 5.0, Version 1.0 (May 28, 2019)("PCIe Gen5 Protocol"), or PCI Express(TM) Base Specification Revision 6.0, Version 1.0 (January 11, 2022) (the "PCIe Gen6 Protocol"), all of which are incorporated by reference in their entirety. shall be taken as a thing. In this case, the protocol analyzer implemented by UI computer 110 may be, for example, a U4301B PCIe Protocol Analyzer, or a U4305B PCIe and LTSSM Exerciser available from Keysight Technologies, Inc.

In the illustrated embodiment, interposer circuit 120 includes a capture buffer 125 for temporarily storing data transmitted between DUT 140 and host computer 150, as described above. Interposer circuit 120 may include a field programmable gate array (FPGA) and/or an application specific integrated circuit (ASIC) (i.e., an FPGA and/or an ASIC); Any processing unit (eg, processing unit 810) capable of performing the functions of interposer circuit 120 described below with reference to FIG. 2 may also be incorporated without departing from the scope of the present teachings. In one embodiment, interposer circuit 120 is implemented by an FPGA having internal high bandwidth memory (HBM) dynamic random access memory (DRAM) available from Xilinx, Inc., for example. and is used as a capture buffer 125.

FIG. 2 illustrates how an interposer can be used without loss of functionality and without loss of information available for analysis during communication of data over a data link that conforms to a high-speed layered packet-based protocol, according to an exemplary embodiment. 1 is a simplified flowchart illustrating a method for reducing the amount of data stored in a circuit's capture buffer. The various steps of FIG. 2 can be performed by interposer circuit 120, as described above. This method provides the UI computer 110 and interposer circuit 120 with a protocol analyzer. This eliminates the complex wiring and signal integrity issues associated with traditional solutions, reduces total cost, and allows the use of high-bandwidth interfaces (with reduced raw data), for example. to support faster upload times.

Referring to FIG. 2, the amount of data stored in the capture buffer is based on four basic steps, each of which will be described in detail below. In block S211, data integrity bits corresponding to a data integrity check of the data performed in real time from the transaction layer packet (TLP) and data link layer packet (DLLP) of the data stored in the capture buffer. Delete. If the data integrity check indicates that the data is correct, the data integrity bit is removed. If not, that is, if the data integrity check indicates that the data is incorrect, the data integrity bits are left in the TLP and DLLP and stored in the capture buffer for analysis by the UI computer 110, according to standard protocols. 125.

In block S212, an acknowledgment (ACK) packet and a negative acknowledge (NACK) packet indicating correct arrival or incorrect arrival, respectively, of the TLP of the data at the intended destination are transmitted. It is not stored in the capture buffer 125. Alternatively, ACK/NACK matching is performed in real time and the ACK and NACK packets are used to confirm successful delivery of the TLP before the ACK/NACK packet is discarded. The ACK/NACK state of the TLP can also be recorded in the capture buffer 125 as metadata.

In block S213, a certain field is deleted from the TLP and/or DLLP of the data or the size of the field is reduced in real time. This removes known fields with fixed or null values, removes framing tokens used to indicate the start and end points of TLP and DLLP packet flows, and eliminates multiple active devices. , including reducing unnecessary fields as a whole to test a single active device and removing non-essential fields that do not have any value for debugging a specific use case.

In block S214, all or part of the TLP and/or DLLP stored in the capture buffer 125 is compressed in parallel. For example, the data payload of a packet may be compressed for storage in capture buffer 125. Compression of the data payload includes, for example, arranging the data in the payload such that each symbol of a wide word is placed in the same location as the next symbol in the next clock cycle of the processing unit. . The arrayed data is then compressed using a hash table that provides pointers to previous symbols already stored in memory. Compression of entire packets (ie, including headers) can be performed in substantially the same way.

[Data integrity check]
Referring to block S211, there are various types of data integrity checks that can be performed in real time and provide data integrity bits that are omitted from storage in the capture buffer 125. In various embodiments, the types of data integrity checks include cyclic redundancy checker (CRC) checks, frame parity checks, and flow control unit (FLIT) checks, each of which is described below. I will explain. The TLP and/or DLLP data integrity bits corresponding to these checks are not stored if the checks indicate that the respective data is correct. Otherwise, if the data integrity bits indicate that the respective data are incorrect, they may be left in the packet and stored in the capture buffer 125 to be analyzed by the UI computer 110.

[CRC check]
For CRC checking, a CRC field containing a checksum is included in the TLP and DLLP of the data. Typically, the checksum is provided in the CRC field of the transmitting device (eg, DUT 105) and obtained at the receiving device (eg, host PC), where it is compared to the checksum of the original data. If the checksums match, it is determined that there is no error in the data. If checksum matching fails, corrective action may be taken, such as requesting retransmission of the packet by NACK, for example. In this embodiment, a CRC checksum indicating no error is deleted from each packet, but a CRC checksum indicating an error is not deleted and is stored in the capture buffer 125.

FIG. 3A shows CRC fields of an example TLP and an example DLLP that should be discarded rather than stored in a capture buffer, according to a representative embodiment. Although the CRC field for TLP and DLLPS is provided, for example, in accordance with section 2.7 of the PCIe Gen3 protocol, the CRC field in other protocols, including, for example, other PCIe protocols (e.g., PCIe Gen4 to Gen6 protocols) may be incorporated without departing from the scope of the present teachings.

Referring to FIG. 3A, the example TLP 310 includes the following two CRC fields. That is, the FCRC field 311 includes 4 bits, and the LCRC field 312 includes 32 bits. Exemplary DLLP 320 includes a CRC field 321 that includes 16 bits. As previously discussed, rather than storing the FCRC field 311, LCRC field 312, and CRC field 321 in the capture buffer 125, the interposer circuit 120 itself first checks the CRC checksum. Checksums indicating no errors are not stored in the capture buffer 125 and are removed from each packet, but checksums of CRCs indicating errors are stored in the capture buffer 125 as usual. For example, an error-free checksum can be removed from each packet. Normally, when a CRC error does not occur, the storage area stored in the capture buffer 125 in units of packets is known and fixed (for example, 36 bits for TLP 310 and 16 bits for DLLP 320).

The data transfer infrastructure from capture buffer 125 to UI computer 110 may be assumed to preserve data integrity, so there is no loss of functionality by omitting the CRC. Thereafter, if no errors occur, the CRC can be statically reconstructed on the UI computer 110 using the inverse of the algorithm used by the sender of the PCIe link to initially calculate the CRC. This way, the user will not be aware that the checksum has been omitted. For example, FIGS. 2-38 of Section 2.7 of the Gen3 protocol illustrate an ECRC algorithm for computing a 32-bit ECRC for TLP end-to-end data integrity protection. UI computer 110 may use the inverse of this algorithm to reconstruct any ECRC previously removed from TLP 310. It will be appreciated that other known algorithms for calculating the CRC may be incorporated without departing from the scope of the present teachings, including, for example, algorithms provided from other PCIe protocols (e.g., PCIe Gen4-Gen6 protocols). Can be done. If there is a CRC error, the TLP 310 and/or DLLP 320 with the CRC error is stored unchanged in the capture buffer 125 so that the CRC can be fully analyzed with a protocol analyzer.

[Frame parity bit]
The frame parity bit is included in the TLP and is also checked on interposer circuit 120. Generally, frame parity bits are checked to ensure that the receiving device is correctly observing the corresponding framing token. In one embodiment, frame parity bits indicating no errors are omitted from being stored in capture buffer 125, and frame parity bits indicating errors are stored in capture buffer 125. The value of the frame parity bit is determined according to the frame parity check. An example of performing a frame parity check is described in section 4.2.2.3.1 of the PCIe Gen3 protocol for framing tokens. It will be appreciated that other known processes for performing frame parity checking, including, for example, processes provided by other PCIe protocols (e.g., PCIe Gen4-Gen6 protocols), may be used without departing from the scope of the present teachings. , can be incorporated. Typically, a framing token specifies or suggests the number of associated symbols and thus the location of the next framing token. For example, a framing token can be a special symbol that indicates the beginning of a packet and allows different types of packets to be quickly and easily identified.

Referring again to the example of FIG. 3A, TLP 310 also includes a frame parity (FP) field 313 that includes one bit as a frame parity bit. Again, rather than storing the FP field 313, the interposer circuit 120 first checks the frame parity bit. If the frame parity bits indicate that there are no errors, the frame parity bits are removed from each TLP 310 before the TLP 310 is stored in the capture buffer 125. If the frame party bit indicates an error, the frame parity bit remains in TLP 310 and is stored in capture buffer 125 as usual for analysis by UI computer 110.

Removing frame parity bits that indicate no errors results in a small savings of only 1 bit per TLP 310. However, typically the packet decoder checks the frame parity bits to ensure that, for example, the source TLP (STP) token (framing token) in the TLP 310 is correct and observes a properly formed TLP 310 in the data stream. need to be confirmed. For example, interposer circuit 120 checks the frame parity bit and STP token so that it can record the start of the corresponding packet and insert a timestamp accordingly. Interposer circuit 120 must decode headers and recover packet boundaries so that filtering can be applied and metadata can be inserted. Regardless of the compression technique that may be applied, the packet boundaries on the interposer circuit 120 need to be calculated, so it is worthwhile to remove the frame parity bit even if only one bit is saved.

[FLIT check]
Some high-speed data protocols use forward error correction (FEC) (eg, PCIe Gen6), in which case the packets must be of a fixed length, such as 256 bytes. Fixed length packets are called flow control units (FLIT). Each FLIT may include one or more TLPs, typically of variable length, for a predetermined number of bytes. For TLPs longer than a FLIT, the TLP is divided into multiple FLITs. Generally, upon receiving a FLIT, a receiving device (eg, host computer 150) performs FEC decoding to correct correctable errors within each FEC group within the FLIT. After FEC decoding, perform a CRC check. If the CRC check fails, the receiving device indicates that the FLIT was not successfully received. This can be done by sending a negative response back to the sending device (eg, DUT 140).

FIG. 4 shows an exemplary FLIT 400 for a 16 lane PCIe link. In the illustrated example, FLIT 400 includes 256 bytes, which are allocated as follows. That is, the first 236 bytes are allocated to one or more TLPs (bytes 0-235) and the next 6 bytes are allocated to the data link layer payload (DLP) (bytes 236-241 are shown as DLP0-DLP5). ), the next 8 bytes are assigned to CRC411 (bytes 242-249 are shown as CRC0-CRC7), and the last 6 bytes are assigned to FEC412, denoted as error correction code (ECC). (Bytes 250 to 255 are illustrated in, for example, three groups ECC0[0:1] to ECC2[0:1]). After executing FEC, CRC check is performed on FLIT400. If the CRC check passes, both the CRC information of the CRC 411 and the FEC information of the FEC 412 are discarded on the interposer circuit 120. The CRC411 is 8 bytes, and the FEC412 (or ECC) is 3 blocks of 2 bytes, each of which is placed at the end of the 256-byte FLIT. Therefore, by discarding the CRC 411 and the FEC 412, 14 bytes out of the 256 bytes of the FLIT 400 are not stored in the capture buffer 125. Note that since the TLP encapsulated in FLIT does not have its own CRC, a FLIT CRC check can be performed instead of a TLP CRC check, as described above with reference to Figure 3A. be.

[ACK/NACK]
Referring to block S212, ACK and NACK matching is performed in real time to confirm successful delivery of the TLP of related data using the ACK packet and NACK packet in real time. Next, the ACK packet and NACK packet are discarded, ie, they are not stored in the capture buffer 125. Generally, the data link layer uses an acknowledgment and negative acknowledgment mechanism to help ensure the delivery of transaction layer packets. In general, each TLP's successful or failed arrival from a source (e.g., DUT 105) at a destination (e.g., host computer 150) is determined by a sequence number that matches the sequence number in subsequent DLLPs. Will be reported back. This sequence number is used to track between the TLP and both ACK and NACK packets (equivalent to DLLP), thereby tying matching sequence numbers across TLP and DLLP to indicate successful delivery. shows. A timer can be used to time the reception of a TLP and its corresponding acknowledgment. If the timer expires (timeout) before the destination receives an acknowledgment (ACK packet), the original data is retransmitted with a new TLP. TLP and DLLP sequence numbers may be reused (wrap around), but in this case live packets may be "in-flight" when the sequence numbers are reused. Must not be.

As mentioned above, interposer circuit 120 omits ACK and NACK packets from being stored in capture buffer 125. Of course, this feature can be disabled if the system is debugging problems, especially the acknowledgment itself. In one embodiment, the TLP may have metadata appended thereto in the capture buffer 125 indicating the acknowledgment status of the TLP, even though the ACK and NACK packets themselves are not stored. Metadata is logically appended to the TLP by interposer circuit 120 before the TLP is stored in capture buffer 125. Therefore, by collating ACKs and NACKs in the interposer circuit 120 without storing ACK packets and NACK packets, and indicating the results of ACKs and NACKs in metadata, virtually "lossless" data compression can be achieved. It can be realized.

This method involves some cost. As discussed above, the exact arrival times of ACK and NACK packets are lost unless time stamps of ACK and NACK packets are added to create richer data. Adding a timestamp to the metadata increases the amount of data that should be stored in the packet buffer, but this increase is less than the amount of data that would originally be stored for the entire ACK and NACK packet. Given the sequence number from TLP 310 and the timestamp associated with the ACK or NACK packet (as appropriate), DLLP 320 can be completely rebuilt unless there is an underlying protocol error. Of course, if there is a fundamental protocol error, all DLLPs 320 should be stored. Further, the timestamp of the DLLP 320 may be maintained as a difference from the original timestamp of the corresponding TLP 310. This reduces the number of bits required for storage while still allowing the location of DLLP 320 in the packet stream to be recovered.

FIG. 3B shows a sequence number field in the same TLP 310 and the same DLLP 320 as shown in FIG. show. Referring to FIG. 3B, TLP 310 includes a sequence number field 314 and DLLP 320 includes a DLLP sequence number field 324. A match between the sequence numbers indicates successful delivery and should result in an ACK of the TLP packet. For example, if a pair of sequence numbers, one sequence number in TLP 310 and one sequence number in DLLP 320, match, TLP 310 is acknowledged (ACKed). In this case, sequence numbers in sequence number fields 314 and 324 are not stored, but a 3-bit symbol indicating whether a TLP 310 and/or an ACK and/or a NACK has arrived is stored. Since the sequence numbers are ordered in each direction (eg, up and down), it can be determined later which sequence number each 3-bit symbol refers to. In the illustrated example, the size of the ACK and NACK packets, and thus the space saved per TLP, is known and fixed. For example, in section 3.4.1 of the PCIe Gen3 protocol, in non-FLIT mode, each TLP 310 has a 64-bit ACK or NACK packet, so as discussed above, the metadata indicating the ACK/NACK status is By adding 3 bits of data and storing it in the capture buffer 125 in association with the TLP 310, it is possible to save 61 bits. For example, section 3.5.1 of the PCIe Gen 6 protocol also mentions the handling of ACK and NACK packets. Furthermore, by enabling FLIT mode in the PCIe Gen6 protocol, we achieved a savings of 6 bytes per FLIT. For example, ACK and NACK packets in other known protocols, including other PCIe protocols (eg, PCIe Gen4-Gen5 protocols), may be incorporated without departing from the scope of the present teachings.

[Delete/reduce field]
Referring again to FIG. 2, in block S213, certain fields of the TLP and/or DLLP are deleted or the data in the fields is reduced in real time. There are several types of fields that can be included in this compression technique. For example, known fields with known fixed or null values, framing token fields that indicate the start and end points of a packet flow, and non-required fields that have no value for a given use case can be removed. Also, fields that are wider than necessary under test conditions may be reduced.

[Remove known fields]
Some TLPs include fields with known values, including fixed values and empty values. Typically, protocols are designed to be regular in nature, inter alia, with respect to common header fields that precede payload data, for example. This is also a frequently considered part of layered protocol design, as it reduces the amount of work required in building the state machine used to decode the protocol. Therefore, many packet types have fields that are used in some packets, but have fixed, known values, or even empty values, for other types of packets. For example, in various packets, a reserved field that must be 0, a traffic class indicator that must be 0 due to unused (because there is always a single data word (e.g. 4 bytes) in the payload), 1 There is a length field that must be .

Also, some packets have known filter settings (eg, known as triggers in PCIe Gen3 protocol software). For example, if you are searching for several talkers on the bus or testing a single endpoint device, the device address field is known in advance and the filter is functioning correctly. , only matching packets are stored. For example, a filter that includes two talkers only needs to identify two known talkers, so it does not require a large address space and data in the address field can be reduced. In some cases, a 16-bit address can be reduced to just 1, 2, or 3 bits.

Although known fields with known (fixed or empty) values may differ for each packet type, it is relatively easy to define these fields and omit them when storing packets. Since the field value is known, it can be recovered by the user interface as long as the interposer circuit 120 checks whether the known value is correct and then omit it from the capture buffer 125. Of course, if it differs from the expected known value, the entire packet, including the known fields, must be stored for later debugging.

FIG. 5A illustrates known fields of an example Config Read TLP that should be discarded rather than stored in a capture buffer, according to a representative embodiment. The known fields of the Configuration Read TLP are provided according to the PCIe Gen3 protocol, such as Section 2.2.6.3 for the Attribute field (Attr), which includes, for example, Provides further information. Referring to FIG. 5A, the following rules apply to the Read Configuration TLP 330. That is, the TC field 331 is 000b, the TH field 333 does not apply to configuration requests, the bit is reserved (probably 0), the Attr[2] field is reserved (probably 0), and the A[ 1:0] field 334 is 00b, the AT field 335 is 00b, the length field 336 is 00 0000 0001b (one), and the last DW BE field 337 is 0000b. Fields 332, 338, and 339 are marked as reserved and are zero. Other known fields of the PCIe Gen3 protocol, as well as other protocols, including, for example, other PCIe protocols (e.g., PCIe Gen4-Gen6 protocols) may be incorporated without departing from the scope of the present teachings. I can do it.

[Framing Token Removal]
Various tokens are symbols used to indicate the start and end points of TLP and DLLP packet flows. A framing token can be replaced with a shorter symbol after confirming its value. In one embodiment, the framing token is checked for each value, and if a value is found to be incorrect, an exception or exception is raised to replace the value with a smaller but unique bit sequence. Again, as the data is extracted from capture buffer 125 and transmitted to UI computer 110, its integrity and spacing shall be preserved by the transport system that transports the packets.

FIG. 3C illustrates framing token fields of TLPs and DLLPs that should be discarded rather than stored in a capture buffer, according to an exemplary embodiment. FIG. 3C shows the same exemplary TLP 310 and DLLP 320 shown in FIG. 3A discussed above. Referring to FIG. 3C, TLP 310 includes an STP field 315 and DLLP 320 includes an SDP token number field 325. The STP field 315 contains the originating packet flow token of the TLP 310 (the field containing the destination packet flow token is not shown), and the SDP token number field 325 contains the framing token of the DLLP 320. Each of the STP field 315 and the SDP token number field 325 may be deleted or replaced with a shorter symbol, for example.

[Reduce fields]
As previously discussed, some packet fields within the protocol are wider (using more bits) than expected to be needed at DUT 140. For example, a system often tests a minimal configuration (a single device). Therefore, compared to a live system where multiple PCIe devices (cards) are used, such as a sound card, graphics card, multiple accelerators, etc., only one active PCIe device communicates with the host computer 150. can. Therefore, if only one or two PCIe devices (eg, DUT 140) are active, there is no need for an address space that can accommodate multiple PCIe devices.

In one embodiment, if the system under test (including DUT 140) has fewer active DUTs than the live system, the size of the address field is reduced depending on the number of active DUTs required and instead a lookup table may be expanded. For example, if there are only two or three active DUTs, the address field can be reduced from 16 bits to only 1, 2, or 3 bits, respectively. By parameterizing the size of the lookup table at startup of the interposer circuit 120, the user can configure memory compression in the UI computer 110 to maximize the use of available memory relative to the number of DUTs. .

Additionally, the Requester (sender) and Completer (receiver) addresses are a mirrored pair of values. If only two parties are participating in the conversation (eg, one DUT 140 and one host computer 150), there will be only one unique pair. Furthermore, since the interposer circuit 120 is directionally aware by virtue of being physically connected to both the downlink and uplink channels as a "man in the middle," no addressing scheme is required. There are cases. In this case, the entire address field can be removed.

FIG. 5B is a diagram illustrating reducible fields of a configuration read TLP to be reduced in size prior to storage in a capture buffer, according to an exemplary embodiment. FIG. 5B shows the same example configuration read TLP 330 shown in FIG. 5A previously discussed. Again, a reducible field in the configuration read TLP is provided, eg, in accordance with the PCIe Gen3 protocol. Reducible fields of other known fields of other protocols may also be incorporated without departing from the scope of the present teachings, including, for example, other PCIe protocols (eg, PCIe Gen4-Gen6 protocols).

Referring to FIG. 5B, the reducible field 340 includes address data related to the sender of the TLP 330, such as bus number (requester), Dev# (Req) (i.e., device number (requester)), and Func#. (R) (i.e., function number (request side)), as well as address data related to the recipient of TLP 330, such as bus number (completer side), Dev# (Compl) (i.e., device number (completer side)), and Funct#(C) (ie, function number (completer side)). In one embodiment, all but 2-3 bits may be removed from reducible field 340. The number of bits is system specific, but only as many bits as there are active combinations of the above fields are required. Meanwhile, a lookup table is created that stores the minimum length aliases of the actual PCIe addresses of the requester and completer of the original packet. Parameterizing the size of the lookup table at startup of the interposer circuit 120 allows the user to configure the UI computer 110 to maximize the available memory compared to the number of addressable entities (e.g., DUTs). You can configure memory compression in

[Remove non-essential fields/packets]
Entire fields that have no value in a given use case can be removed from the TLP and DLLP. Entire packets with no value may also be deleted. Furthermore, TLPs and DLLPs with large/long payloads can also be truncated. That is, there are many packet types with each field not important when debugging a particular use case. Such packets and/or fields within the packets (ie, the packets, fields within the packets, or both) may be omitted depending on the user's configuration. For example, based on UI settings, a list of packets and/or per-packet fields (packets and/or per-packet fields) that can be removed from the capture stream may be provided. This would result in a "lossy" compression since deleted packets and/or fields (ie, packets and/or fields) cannot be reconstructed at the UI computer 110. This storage method also requires specifying which fields are present at runtime. Therefore, rather than a fixed storage scheme, a flexible storage scheme is implemented that maximizes storage capacity when fields are deleted. It should be noted that if an entire field is removed or a packet is truncated, the data integrity check values discussed above may not be recovered losslessly at the UI computer 110.

[Parallel compression]
Referring to block S214, the TLP and/or DLLP payload of wideword data stored in the capture buffer is compressed in real time. Compression is not done serially as in conventional compression techniques, but rather in parallel. In one embodiment, the header may also be compressed in real time along with the TLP and/or DLLP payload. The discussion below focuses on data payload compression for ease of explanation, but can be applied to full packet compression without departing from the scope of the present teachings.

By way of background, it is generally understood that the compression output in known compression algorithms, such as those based on LZW, LZ77, and LZ78, and the dictionaries required for compression, are limited to one symbol of input data at a time. The content of such a dictionary depends on knowing the location of previously occurring patterns in the stream. Therefore, compression algorithms with such dependencies are difficult to process in parallel.

In general, parallel processing improves efficiency, such as by parallelizing compression algorithms in one step with a single processing unit that processes multiple symbols simultaneously. Such a strategy is sometimes referred to as single instruction multiple data de-skewed lane (SIMD) processing, or "wideword" processing, where a wideword consists of multiple symbols (e.g., 4, 8 , 16, or more symbols) as well as a single circuit, with each symbol typically representing one byte of data, with all operations involving multiple bytes per operation. Equal. Applying to PCIe, each single PCIe lane's data already carries multiple bytes per clock cycle. However, because the PCIe analyzer handles data in combined deskew lanes rather than multiple single PCIe lanes, the final deskew data bus can be 128 bytes, 256 bytes, or more wide. In this case, since conventional data compression does not require each symbol to be 8 bits wide, a symbol can be considered to consist of multiple bytes of data. However, in general, compression algorithms use 2^ ⁸ (2 ⁸ )), the compression efficiency is worse, and the compression algorithm as a whole consumes much more memory since the size of the dictionary increases by 2n, where 'n' is the bit width.

For example, a wide word design requires a change in the word size of the dictionary (eg, a 256-byte change) so that the dictionary can track the data rate of each clock input in real time. It takes one clock cycle in hardware to write a single change to single-ported memory, and given that word-sized (e.g., 256 bytes) changes are being made, it is possible to keep up with the data. , 256 memory blocks are required in this example to obtain the required number of memory ports to avoid data loss. Further, conventional FPGAs are equipped with block random access memory (BRAM), but the size of each BRAM is as small as 36K bits, and a plurality of BRAMs are required for each of 256 dictionaries. Even the largest current FPGAs do not support enough BRAM to efficiently implement this many dictionaries. In a wideword (e.g., SIMD) implementation that processes data at line rate, each addition to the dictionary requires one memory write operation and one memory read operation, with each operation requiring one clock It takes cycles, and since it uses one memory port (i.e. two memory ports total), one change is required for each new multi-symbol compressed code computed when reading a wideword. Become.

Since BRAM is a twin port, it can perform only one write operation and one read operation per clock of each clock cycle. Therefore, the compression algorithm requires multiple BRAMs (more generally, multiple ports). Having multiple BRAMs reduces so-called "memory latency" so that each update can be written via a separate memory port in a single clock cycle. However, if the number of memories, such as BRAM, is the same as the wideword width, there will be at least 256 memories, and each memory will contain only one word size of a new dictionary entry. As such, multiple memories are inherently non-coherent. That is, each full memory block is fragmented with compression dictionaries distributed across multiple word-sized memories. It may be possible to keep memory coherent if more clock cycles are available, but the real-time constraints of compression algorithms make it difficult to synchronize memory with another algorithm.

To address these issues, various embodiments provide compression algorithms in which memory fragmentation in symbol wide word (SIMD) implementations is not an issue. FIG. 6 illustrates an example of a wideword data symbol configured to enable parallel data compression in a single circuit, in accordance with a representative embodiment.

Referring to FIG. 6, serial stream 620 includes symbols (bytes) b0-b10 in each wide word. It will be appreciated that serial stream 620 is received over multiple lanes according to a high speed protocol (eg, up to 16 lanes for PCIe Gen6 protocol). To simplify explanation, each wide word consists of four symbols in the illustrated example, as opposed to 256 symbols in the more common implementation. For example, a first wide word includes bytes b0, b1, b2, and b3, and a second wide word includes bytes b4, b5, b6, and b7. Assume that each symbol is a byte with, for example, 8 bits. Traditional compression algorithms compress serial streams "as is", ie, each symbol is followed by the next symbol in the serial stream.

However, in the illustrated embodiment, rather than using the next symbol of the serial stream, as in conventional compression algorithms, the data stream uses a wide word of the next four symbols of the data stream in the next clock cycle. Arranged to provide an input stream where each symbol is followed by the next symbol from the same location. That is, if there are four symbols per wideword, the symbols are grouped into every fourth for compression, as indicated by the different shadings in the serial stream of symbols indicated by reference numeral 630. Therefore, in this example, bytes b0, b4, b8, . ．． ．． forms a first input stream 631 for the first dictionary (D1), containing bytes b1, b5, b9, . ．． ．． forms a second input stream 632 for the second dictionary (D2), containing bytes b2, b6, b10, . ．． ．． forms a third input stream 633 for the third dictionary (D3) and contains bytes b3, b7, b11, . ．． ．． forms a fourth input stream 634 for the fourth dictionary (D4), each wide word having four symbols. The set of bytes at the same location in the first to fourth dictionaries (ie, each column of the array shown in FIG. 6) is then compressed every clock cycle. More generally, compression is performed on the first through nth dictionaries, where n is the number of symbols per wideword. This allows effective parallel compression.

In other words, assume that the data stream is provided as bits expressed as "abcd efgh ijkl mnop". For the above input, the conventional LZW compression algorithm uses, for example, sequential unique pairs "ab", "bc", and "cd" for one wide word, "ef", and "cd" for the next wide word. New dictionary entries are created such as "fg" and "gh". In the conventional LZW compression algorithm, "a", "b", "c", "d" . ．． ．． It is output like this. At any stage in the process, if a multi-symbol string can be compressed by combining two or more symbols into a single new output symbol (code), the compression algorithm will do so. Become. When this occurs, there is a significant gap in the output before the new compressed symbol is output.

However, in accordance with various embodiments, again assuming for the sake of illustration a wide word size of 4 symbols, for each compression step for n>=0, as discussed below, (4n+i) The th symbol (i=0, 1, 2, or 3) is considered. In this case, a new dictionary entry is paired as follows in a separate memory every clock cycle with consecutive clocks and four ordered inputs (1-4), each input addressing a different dictionary. be done, therefore,
1) ae, ei, im, . ．． ．．
2) bf, fj, jn, . ．． ．．
3) cg, gk, ko, . ．． ．．
4) dh, hl, lp, . ．． ．．

That is, to support fragmented memory of the dictionary, symbols are effectively presented to the compression algorithm as a value of all "(word_size*n+input_stream-1)" in each clock cycle "n". Each sequence then creates a new multi-byte symbol if that symbol has not been observed before. If the wide word size is 4, as in this example, then the compression algorithm uses four separately fragmented dictionaries, one for each value of i, for every (4n+i)th value ( i=0, 1, 2, 3). Therefore, as shown in Table 1, four blocks of four symbols will be encoded into four memories, such as "aeim", "bfjn", "cgko", and "dhlp". Data is processed as multiple streams for one memory "unit", so one dictionary (hash table) is processed per stream (e.g. each dictionary contains one or more FPGA memories). obtain).

Reading the columns of the array shown in Table 1, the pair of bytes "ae", "ei", and "im" are the inputs to the first dictionary in successive clock cycles. In the last clock cycle, the letter "m" is the last symbol in its sequence, and since there are no subsequent symbols to form new pairs that will be used for later compression, a new dictionary is added to the first dictionary. Do not add entries. Similarly, bytes "bf", "fj", and "jn" are inputs to the second dictionary in consecutive clock cycles, etc., and bytes "cg", "gk", and "ko" are input in consecutive clock cycles, etc. The bytes "dh", "hl", and "lp" are inputs to the fourth dictionary at consecutive clock cycles, etc. from the fourth clock cycle onwards.

In a simple implementation of dictionary D, an array may be used such that D[i] is stored in the i-th (i=0, 1, . . . , word_size−1) element. However, since the length of the strings in dictionary D is variable, a simple implementation would not be efficient or trivial on the fixed memory provided by the FPGA. A simple software implementation of dictionary D could, for example, use variable-length strings as keys and associative arrays with compressed codes as values, which could be implemented as a balanced binary tree. can. However, each memory lookup to check by the binary tree whether the code is already known requires O(log(n)) operations, where n is the stored character is the number of column/integer pairs. Real-time operation on an FPGA requires O(1) operation, which means that the FPGA has only one clock cycle to compress the real-time data into one or more dictionaries D. . Furthermore, in an FPGA, it is necessary to define and fix the memory size during programming of the FPGA, so it is not easy (nontrivial) to store variable-length character strings as keys in the FPGA. Conversely, for decoding, each compressed codeword (key) can point to a string of unknown variable length bytes (values), which again is not trivial in FPGAs. During decompression, the reverse lookup result of dictionary D is stored in the FPGA so that one uncompressed (clear code) byte is released every clock cycle.

According to various embodiments, a sequence of bytes to be compressed, ie, a variable length string, is stored as if it were a string in the programming language "C". That is, each byte string is stored as NULL in a multi-character terminal list, along with a pointer that allows traversal of the entire list. This solves the problem associated with storing variable length strings in an FPGA. A byte string (string) is not a strict array as in the standard "C" programming language, but rather a singly linked list, where each link stored with each character points to the previous character in the string. It is very similar to the data structure of list). Such a linked list data structure is sometimes referred to as a "reverse-pointer table." This design allows the compressed code to point to variable length patterns in FPGA memory without loss or error. Hash tables are accessed via hash functions in hardware rather than simple binary trees. The combination of hash functions and inverted pointer tables supports real-time memory accesses that require one read per clock cycle and one write per clock cycle.

The reverse pointer table can be implemented using at least one FPGA with high-density, single-clock, two-port, synchronous memory, such as the UltraRAM of the UltraScale+™ FPGA available from Xilinx, Inc., for example. However, it should be understood that an FPGA and associated RAM having substantially the same functionality as the UltraRAM discussed below may be incorporated without departing from the scope of the present teachings. Typically, UltraRAM has eight times the storage capacity of conventional BRAM used in FPGAs, so conventional FPGAs, for example, cannot include enough BRAM in the 256-wideword design considered herein. I can't.

Because UltraRAM is compatible with the FPGA's columnar architecture, you can instantiate multiple UltraRAMs in the FPGA and cascade them directly in a single column for the entire height of the FPGA. is possible. UltraRAM includes 288 Kb single clock synchronous memory blocks arranged in one or more columns of the FPGA, with each memory block configured as a 4K x 72 bit memory block that can store up to 288 Kbits of data. A single clock domain column of an FPGA includes 16 memory blocks.

Each UltraRAM has two ports, both of which address all 4K x 72 bits of each memory block. A single URAM has eight times the capacity of a single BRAM, as mentioned above. These two ports can each independently perform either one read operation or one write operation per clock cycle. However, internally, the FPGA's static random-access memory (SRAM) array uses single-port memory cells. Dual port operation is performed by operation of the first port followed by operation of the second port in a single clock cycle, the first port and the second port sharing a single clock input.

The reverse pointer table can be implemented using a hash table or dictionary that achieves the required O(1) operation a priori on the FPGA. In general, dictionaries are implemented in hardware as hash tables, but in software they can be implemented as binary trees. The hash table (dictionary) includes two separate sub-tables: a number table and a data table, as shown in Table 2 below. Each element of the number table stores the number of entries used in the data table with two entries per row. In the FPGA, it is determined whether an encoded symbol (a string) is already known or whether a new code needs to be created. To do this, each hash entry has a compressed code of up to 12 bits, which can be up to 14 bits, and 8 Requires a bit character (the last symbol in the string) and an equal-sized inverted pointer to the previous symbol in the string.

Each data table is implemented with one (or two) UltraRAM, e.g. to perform a hash function on wideword data stored in parallel, and each number table is implemented with two ( Or, it is implemented with 4 BRAMs. The hash size matches the UltraRAM address space (4K x 72 bits) and uses 72 bits of data at each memory location to form two 36-bit entries, as shown in Table 2. Can be done. Therefore, the data layout of UltraRAM has the same total memory footprint as, for example, eight BRAMs, but is "narrower" and "deeper" than, for example, the eight 36-bit entries required by BRAM. ” has become.

The number table indicates the used capacity of the data table. Therefore, if UltraRAM is used for the data table, word size *UltraRAM (possible 256 UltraRAM, which corresponds to about 20% of a conventional large-scale FPGA), and word size *2 * BRAM (possible 512 BRAM). ) is obtained. In Table 2, the entries e _h,i in both columns (e.g. e _0,0 , e _1,0 , e _2,0 , ... and e _0,1 , e _1,1 , e _2,1 , ...) are each a structure containing three values: a pointer (j), the last byte of the symbol string being compressed, or (x), and an inverse pointer computed from j and x. For example, if the string to be compressed is the word "cat", entry e ₀₀ is "t", which may be a reverse pointer to another entry. The reverse pointer may have "a" and a reverse pointer to yet another entry, and the reverse pointer may have "c" and a reverse pointer to NULL. NULL indicates that there is no reverse pointer and indicates that it is the starting point of the multi-symbol string. This arrangement solves the problem of variable length strings in the dictionary. Note that each column in Table 1 is equivalent to a string of input symbols in FIG. For example, the first column of Table 1 may correspond to the first input stream 631 of the first dictionary of FIG. Similarly, there is one Table 2 for each column in Table 1, and thus for each input stream in FIG. So, for example, a 256 wideword design (different from the 4 wideword design of FIG. 6) would effectively provide 256 different instances of Table 2.

As another example regarding compression, a string to be compressed in one input stream (e.g., first input stream 631), and thus a string addressing one dictionary (e.g., first dictionary), is , "a b ab aba b" (without spaces, but spaces are included here for clarity), in which case the string compressed according to the LZW compression algorithm is, for example, It should be 97 98 256 258 98. The first "a" and the first "b" cannot be compressed because they are the first occurrences of these characters, but if the letters "a" and "b" were observed first, then the code 256 would be compressed. When a new multi-symbol string "ab" is added to the first dictionary used, and then a second occurrence of "ab" is seen in this stream, this new code is added to the second occurrence of "ab". ”, the multi-symbol string is compressed into a single code. Similarly, when "ab" is first observed, there is an opportunity to create a new multi-letter code "aba" with value 258 in the dictionary. Note that although the character code "ba" was assigned the value 257, "aba" with the value 258 is preferred since the algorithm automatically maximizes compression. When a second occurrence of "aba" is observed, this new code can be used in a multi-symbol string. Note that the outputs for "a" and "b" are just the (illustrative) numerical representations 97 and 98 of the letters "a" and "b", respectively, in the ASCII table.

For "ab", there will be an entry in the dictionary that includes the previously occurring character and has reverse pointers: 256, x: 98, j: 97. Character x: 98 (ie, character "b") and pointer j: 97 (ie, character "a") are temporarily output. In this case, pointer j simply points to the character "a". Since "a" and "b" are reversed, when decompressed, the compressed value 256 becomes "ab". The entry appears in the dictionary at row h(j=256,x=97)=512 and is likely to be e _512,0 unless some other hash function has previously provided 512, in which case , the entry should be e _512,1 . If something like this happens again, a conflict will occur and this new multi-symbol string will not be added to the dictionary (compression has to be done in one clock cycle, and it would otherwise have handled the conflict). (there are several methods), the compression efficiency will be slightly worse. Therefore, the hash function h(j, There is a need to.

Continuing this example, for "aba", there is an entry (calculated by h(j, x)) in the dictionary that includes the previously occurring character and has reverse pointers: 258, It turns out. The character x: 97 (that is, the character "a") and the pointer j: 256 are temporarily output. Pointer j:256 moves to its previous location and the reverse pointer becomes 256. In this case, following the same procedure as above would again provide the output of "ab" added to the previous character, resulting in "aba". The word "aba" here is actually reversed, but in this example, there is no problem. If the order of the characters matters, for example, in the string "cat" example above, the order would be reversed when decompressed. The output of "aba" is 258. Since the last character is simply a "b" and there are no more strings to concatenate, the output is simply 98 (ie, the character "b").

Of note, UltraRAM is not as flexible or high-performance as BRAM, so data reaches clock/line rate with one compression operation per clock cycle, and there is no delay between read and write operations. Each time a new delay occurs, a new delay may occur. To mitigate this risk, up to 'n' new Additional clock cycles can be added to run the compression algorithm. This results in the encoding and decoding algorithms operating correctly even though new latencies are introduced, but compared to, for example, traditional LZ77 or LZ78 compression algorithms, the new codeword 'n' Not being available until after a clock cycle may degrade compression slightly.

The hash function h(j,x) implemented using Table 2 is implemented in Equation (1), where “>>” and “<<” represent bitwise right shift and left is a shift, "^" represents a bitwise exclusive OR (XOR) operation, and "&" represents a bitwise AND OR.
h(j,x)=((j>>4)^(j<<2)^(x<<4))&"0xFFF" Formula (1)

The hash function h(j,x) has two input parameters: a 12-bit inverse pointer (j) and an 8-bit character (x). The hash function h(j,x) calculates a new row every clock cycle, eg, the rows are shown in Table 2. Therefore, for example, if h(j=0, x=1)=16, the 16th row of the number table in Table 2 should be accessed. The number subtable in row 16 will contain either 0, 1, or 2, depending on the number of entries filled in the data subtable of Table 2. If the 16th line is 0 or 1, the character x is written to either e _16,0 or e _16,1 . If row 16 is 2 (i.e., this row is full), this is a conflict and the inability to add an entry for this newly hashed string causes this newly hashed string to appear later in the data stream. If detected, compression may be slightly worse than optimal. This character is each symbol, and the reverse pointer associates this symbol with the previous symbol in the array shown in Table 1. The hash function h(j,x) has a 12-bit output address (for example, 4096 different addresses), unlike the 10-bit output address when using BRAM, and has uniform access to all output addresses. can do. In other words, it is assumed that one address is not accessed more often than other addresses. Since the hash function h(j, It is.

As with any hash function, there is a possibility of collisions. A collision is when different strings have the same hash value. If both locations of a line are used, a conflict will occur (as described above), i.e. a new compressed code for the string cannot be added to the dictionary, and an existing The smaller sign shall be used. This compromises some of the expected compression, but allows for real-time operation as a second search that cannot be achieved in a single clock cycle, even when attempting to resolve hash conflicts.

FIG. 7 illustrates parallel data compression of a data payload to be stored in a capture buffer of an interposer circuit during communication of data over a data link that conforms to a high-speed layered packet-based protocol, according to an exemplary embodiment. 1 is a simplified flowchart illustrating a method for

Referring to FIG. 7, performing parallel data compression includes, in block S711, a TLP and/or DLLP symbols are received. At block S712, the TLP and/or DLLP symbols are deskewed into a serial stream of widewords (eg, serial stream 620) that arrives each clock of the clock cycle. At block S713, wide words are arranged into input streams (eg, first stream 631 through fourth input stream 634). Each input stream contains symbols from the same location in each wideword that arrive at each clock of the clock cycle, ensuring that each symbol is placed in the correct location with the next symbol, for inputs up to 256 bytes wide or more. form a stream. That is, the interposer circuit 120 compresses 256 or more data symbols (bytes) at a time from (up to) 16 lanes provided by the high speed protocol to form a wide word to be compressed on each clock cycle. can be acquired and deskewed. In the discussion above, we have assumed that bytes and symbols are each 8 bits, so with respect to widewords and compression, these terms are used interchangeably.

At block S714, the hash function shown in equation (1) is implemented to compress the arrayed symbols using a hash table that provides pointers to previous symbols. In block S715, the compressed symbols are stored in the capture buffer 125. an interposer circuit 120 and/or a UI computer 110 running a protocol analyzer (i.e., an interposer circuit 120 and/or a UI computer 110 running a protocol analyzer) to analyze a data payload according to a high-speed data protocol; The compressed symbols can be decompressed by

The process described above with reference to blocks S711-S715 of FIG. 7 is sometimes referred to as a protocol domain-specific compression technique. This is because each process utilizes a protocol design to compress or reduce the amount of data required to be stored in the capture buffer 125 without losing information. Also, because interposer circuit 120 is acting as a "man in the middle" with respect to DUT 140 and host computer 150, certain assumptions may be made about how protocol traffic is captured and processed. Also, the use case of the host computer 150 and the test itself may further relate to mechanisms for reducing data without compromising fidelity.

As mentioned above, compression can be performed on the TLP and/or DLLP data payload or on both the data payload and the header. When performing compression on both the data payload and the header, all wide words are passed to the compressor unchanged. As previously discussed, if compression is performed only on the data payload, there are other techniques to reduce the amount of data stored for wideword headers, such as removing data integrity fields and removing known fields. and then perform compression on the remaining portion. In one embodiment, the data payload may be reorganized into new 256-byte wide words before compression to first remove gaps to increase efficiency.

[Decompress]
In various embodiments, the compressed data can be decompressed when needed. Decompression does not require access to a copy of the dictionary from the compression stage, but the dictionary can be used. Rather, generally speaking, decompression of compressed wideword data input involves combining the combined compressed Only a copy of the output stream is required. This is particularly useful for the UI computer 110 since only the compressed data is sent to the UI computer 110 via the USB or Ethernet link, and not the full set of dictionaries together with the compressed data. .

Storing the compressed data as a single uninterrupted sequence (stream) provides optimal data storage. However, the order of data in the output stream of data produced by compression is important in correctly decoding symbols. Decompression must be able to identify which compressed symbols belong to each of the individual original wideword input streams (e.g., first input stream 631 to fourth input stream 634). Yes, this allows the symbols after compression to be addressed to the correct dictionary Di (i=0, 1, 2, . . . , wideword-1).

For example, in a conventional LZW compression algorithm, once a compressed symbol is generated, the symbol is written to the output stream. Therefore, when not adapted for wideword systems, the LZW compression algorithm (and other conventional (compression algorithm), ordering information will be lost.

Creating compressed symbols that represent one or more uncompressed symbols will change the order of the compressed output stream of widewords in the capture buffer. FIG. 8 is a diagram illustrating, for illustrative purposes, an example of input symbols for decompressing wideword data generated using the compression technique described above.

Referring to FIG. 8, a first input stream 811 (input stream 0) and a second input stream 812 (input stream 1) of wideword data are input for compression. The first input stream 811 and the second input stream 812 correspond essentially to the first input stream 631 and the second input stream 632 discussed above with reference to FIG. 6, for example, but for convenience: The symbol numbers are different. A first compressed (intermediate) stream 821 (0 after compression) is computed for the first input stream 811 and is an intermediate step between when the data is compressed and just before the data is written to the capture buffer during the compression process. Represents the order of operations in . Similarly, a second compressed (intermediate) stream 822 (post-compressed 1) is computed for the second input stream 812 at the time the data is compressed and just before the data is written to the capture buffer during the compression process. represents the order of operations at intermediate steps. The uninterrupted final compressed single output stream 830 corresponds to data stored sequentially, but as discussed below, the capture buffer is configured to handle no operations in the compressed first stream 821 ( The presence of the no-operation ("NoOp") entry results in an ordering such that the subsequent ordering of the output symbols for decompression purposes is unrecoverable.

In FIG. 8, "bn" indicates the symbol at the nth location of stream "i", and "Di" indicates the corresponding dictionary for stream "i", that is, the i-th dictionary. As with the compression processes considered so far, initially each input stream of wideword symbols (e.g., first input stream 631 to fourth input stream 634) is fragmented from the larger dictionary (D) itself. Each input of the set of wideword symbols is processed separately for decompression. Therefore, it is necessary to use the same collation information when decompressing. In the example of FIG. 8, symbols in the first input stream 811 must address the first dictionary D1, symbols in the second input stream 812 must address the second dictionary D2, and so on. This is the rule.

In general, the inputs and outputs of compression algorithms process data from an operational perspective. During the compression stage, one operation requires a single clock cycle (corresponding to a hard constraint) and the processing of the input data needs to occur in real time. However, during the decompression phase there is no such hard constraint; a single operation can take more than one clock, if necessary. For ease of explanation, we first describe the decompression process from an operational perspective and then provide an example of mapping the operations to clock cycles on hardware (eg, an FPGA, or an ASIC).

Regarding the order of symbols in the output stream 830 after seamless compression, once symbols b5 and b6 are compressed into a single symbol during the compression process, the exemplary compression process shown in FIG. This will cause the output to be skipped at location b5 (action number 5) in the first input stream 811 using D1. This skip is indicated by the NoOp entry of the computed compressed first stream 821 for the first input stream 811 . Generally, a NoOp occurs when a new compressed symbol representing two or more original input symbols is about to be emitted, but has not yet been emitted. This occurs when multiple input symbols are compressed into a single code. For example, compressing two original input symbols results in one NoOp, and compressing three input symbols results in two NoOps. Therefore, each time an input symbol is consumed, the compression algorithm tests whether it can compress that input symbol. If a long multi-symbol string that matches the input symbol is already known, the input symbol can be compressed with that long multi-symbol string. Whenever this occurs, there will be no symbol at that location, so a NoOp entry is introduced. Therefore, a new compressed code representing the newly combined compressed symbols b5 and b6 is not released at the output of the first input stream 811 until symbol b6 (operation number 6).

For non-wideword compression with a single output stream, the new multi-symbol string b5/b6 remains the next symbol serially following symbol b4 in the uninterrupted compressed output stream, so NoOp is not a problem. That is, if there is only one input stream to compress, there is no possibility of reordering occurring. However, in wideword compression, one or more NoOps may change the order of input symbols when combining various input streams into an ideally uninterrupted single output stream. In particular, an optimal, space-efficient layout within the capture buffer requires a single uninterrupted compressed output stream.

In the illustrated example, the presence of a NoOp in the first stream 821 after compression causes the single output stream 830 after compression to correspond to data in the capture buffer that is not properly ordered. As shown, compressed output stream 830 receives symbols alternating between compressed first stream 821 and compressed second stream 822 . In other words, the compressed output stream 830 extracts the symbol b1 from the compressed first stream 821, the symbol b1 from the compressed second stream 822, and the symbol b2 from the compressed first stream 821. Symbol b2 is received from the subsequent second stream 822, and so on. However, by skipping the NoOp entry of the compressed first stream 821, symbol b4 of the compressed second stream 822 is immediately followed by symbol b5 from the compressed second stream 822. Then, the multi-symbol character string b5/b6 from the compressed first stream 821 continues. Since the order ensuring that the first input stream 811 is addressed to the first dictionary D1 and the second input stream 812 is addressed to the second dictionary D2 is lost and cannot be recovered, the compression Using the later output stream 830 as input for decompression makes it impossible to recover the data in each dictionary in its original order. For example, two adjacent symbols b4 and b5 originating from the second input stream 812 appear in consecutive locations in the compressed output stream 830 (indicated by a circle 835), so that the symbols that appear alternately are round robin If we aim for alternating streams in a (round robin) manner, it would be incorrectly assumed that they originate from different input streams. It is also assumed that multi-symbol character string b5/b6 from symbols b5 and b6 starting from the first input stream 811 appears after symbol b5 starting from the second input stream 812. Therefore, a more predictable order is needed to help recover data from multiple input streams in widewords.

One solution is to include additional information indicating the original input stream (eg, first input stream 811 or second input stream 812) and the associated dictionary of each symbol bn. The additional information allows the correct dictionary Di to be addressed. However, after the data is interleaved during compression into a single uninterrupted output stream in the capture buffer, the amount of data after storage is limited to the amount of additional information required to identify separate input streams. Including additional information is counterproductive to the goal of maximizing available data storage. Alternatively, each dictionary's data can be placed in a separate location, effectively creating multiple stripes (rows) of compressed data, one stripe for each dictionary. However, this approach is also not optimal because the capture process stops when the available space in one stripe is used up. That is, when a stripe becomes full, no more data can be written to other stripes in the capture buffer, even if there is still some free space.

In contrast, according to embodiments herein, the compressed data is not reordered because the first symbols of the multi-symbol string are written to the capture buffer in the order in which they originally appear (before compression). Avoided. This is not the location of the symbols when the unbroken compressed output stream is created during compression, but rather the unbroken compressed output stream, as if the unbroken compressed output stream were an uncompressed multi-symbol string. This is done by using the symbol locations of the output stream without compression.

FIG. 9 is a diagram illustrating an example of reordering symbols of a wideword data input for decompression, according to a representative embodiment. Referring to FIG. 9, the compressed multi-symbol string corresponding to the two original arriving symbols b5 and b6 from the first input stream 811 is written in the place of the first arriving symbol b5 and the next It is not written to the location of the incoming symbol b6. That is, as seen in FIG. 8, multi-symbol string b5/b6 is written with action number 5 and not with action number 6. By performing this "first arriving symbol" reordering, sufficient information is retained to restore the original order of symbols b5 and b6 from the compressed output stream 930 stored in the capture buffer. When the combined multi-symbol string b5/b6 is decoded, the multi-symbol b5/b6 is decoded from the original two uncompressed strings for the first input stream 911, which are also known to belong to the first dictionary D1. The acquired data code can be queried as to whether it corresponds to symbols b5 and b6. Therefore, the order is preserved. Also, symbols cannot be written early, and remaining symbols from other streams can be delayed in temporary buffers to buy time to reorder the output.

Specifically, FIG. 9 shows a first input stream 911 (input stream 0) and a second input stream 912 (input stream 1) of wideword data, which are provided below for compression. . The first input stream 911 and the second input stream 912 may respectively correspond to the first input stream 631 and the second input stream 632 discussed above with reference to FIG. are different. FIG. 9 shows the compressed first stream 921 (0 compressed) computed for the first input stream 911 and reordered according to the present embodiment, and the compressed compressed stream computed for the second input stream 912. A second stream 922 (post-compressed 1) is also shown, representing the order of operations at intermediate steps during the compression process before the data is written to the capture buffer as a continuous compressed output stream 930. Subsequent decompression is performed on the compressed output stream 930 according to known decompression algorithms. The final decompressed stream 940 shows correctly ordered decompressed data despite the presence of NoOp entries in the first compressed stream 921.

According to the illustrated embodiment, the compressed output stream 930 for a wideword consists of a first input stream 911 and a second input stream that alternate based on the first symbol in the original location of the uncompressed string. Successive compressed symbols from input stream 912 are written during compression so that they follow each other. If the originally arriving symbol cannot be compressed, it will be emitted at the correct location during correct operation regardless. When one or more symbols are compressed into a multi-symbol string, the final compression algorithm created corresponds to the first symbol of the multi-symbol string, rather than the final operation of the multi-symbol string. The compressed code is temporarily buffered so that it appears as if it were created in the first operation, and then released in the order of the first arriving symbols. This interleaving requires adding an appropriate delay in emitting the symbols of all input streams whenever the input symbols of any one of the input streams are compressed into a new multi-symbol string.

For example, in the exemplary dual wide word system described herein (for ease of explanation), the output after compression is always first input stream 911, then second input stream 912, etc. , released in pairs. Furthermore, whenever we compress multiple symbols into one new multi-symbol string, this new compressed symbol code is written at the location of the first initial/first uncompressed symbol in the new code. It will be done. For example, the compressed multi-symbol string b5/b6 is written at the location of symbol b5 in operation number 5, and is not written at the location of symbol b6 in operation number 6. Thus, in the illustrated example, the compressed output stream 930, in accordance with the representative embodiment, is Represents data in a properly ordered capture buffer.

As shown, compressed output stream 930 receives symbols alternating between compressed first stream 921 and compressed second stream 922. That is, the compressed output stream 930 extracts the symbol b1 from the compressed first stream 921, the symbol b1 from the compressed second stream 922, and the symbol b2 from the compressed first stream 921. Symbol b2 is received from the subsequent second stream 922, and so on. This post-interleaving process includes receiving multi-symbol character strings b5/b6 from the compressed first stream 921 after receiving symbol b4 from the compressed second stream 922, and receiving the multi-symbol string b5/b6 from the compressed first stream 921. 2. Proceeding to include receiving symbol b5 from stream 922 of 2. Next, we are again considering a switched NoOp entry, but it is not written to the compressed output stream 930, so the next symbol is symbol b6 from the second stream 922, Then, symbol b7 of the compressed first stream 921 is received, and then symbol b7 is received from the compressed second stream 922. Therefore, in the illustrated order, it is possible to recover the data for each dictionary in its original order, as seen in decompressed stream 940 (again, indicated by circle 935), and multiple input streams in widewords. You can restore data from. In particular, symbol b6 (illustrated with reference numeral 941) from the compressed first stream 921 is placed right after symbol b5 from the compressed second stream 922.

By performing a "first-to-arrive symbol" reordering (de-interleaving), two pieces of prior information needed to reconstruct the data in the correct order can be preserved. First, in the illustrated example, it is known that the multi-symbol string b5/b6 arrived at the location of symbol b5 of the first input stream 911 rather than at the location of symbol b5 of the second input stream 912. Therefore, it is addressed in the first dictionary D1. Second, by examining the obtained data regarding the multi-symbol string b5/b6, it is found that the length of the final uncompressed string exceeds one symbol. Therefore, when decoding the compressed multi-symbol string b5/b6 to obtain, for example, a decompressed stream 940, when the timing is right, symbol b5 will be written out first and symbol b6 will be written out later. Become. In this way, symbols b5 and b6 are both written into the correct position of the final stream 940 after decompression. Further, since it is known that the final length of the multi-symbol string b5/b6 is two uncompressed symbols, it is possible to calculate the dictionary to which the next code of the compressed output stream 930 belongs. In particular, in hardware implementations using FPGAs (or ASICs), symbols are rearranged in reverse order using the reverse pointer technique discussed below.

That is, if a single code after compression corresponds to multiple input symbols, the length and position of the symbol after decompression can be calculated according to this embodiment. In the example shown, two bytes are shown in the position of byte b5 of the output stream 930 after compression. Using this information, one can calculate how to correctly read the decompressed symbols of all other interleaved input streams to provide decompressed stream 940.

10 and 11 are diagrams illustrating other examples of reordering symbols of wideword data input for decompression, according to representative embodiments. Referring to FIG. 10, it is assumed that the multi-symbol string b5/b6 is located at the position of symbol b5 in each of the first stream and second stream (not shown) after compression. Thus, the compressed output stream 1030 receives symbol b4 from the compressed second stream, followed by multi-symbol string b5/b6 from the compressed first stream, and also receives the compressed multi-symbol string b5/b6 from the compressed first stream. Following the multi-symbol string b5/b6 from one stream, the multi-symbol string b5/b6 is received from the second stream after compression. Therefore, the subsequent stream 1040 after decompression includes symbol b6 from the first stream after compression (illustrated at reference numeral 1041) and symbol b6 from the second stream after compression (illustrated at reference numeral 1042). , with the correct order, as shown by being placed right after symbol b5 from the second stream after compression.

Referring to FIG. 11, a multi-symbol string b5-b7 representing the combined compressed symbols b5, b6, and b7 is at the position of symbol b5 in the compressed first stream (not shown). Assume that Thus, the compressed output stream 1130 receives symbol b4 from the compressed second stream, followed by multi-symbol strings b5-b7 from the compressed first stream, and subsequently further multi-symbol strings b5-b7 from the compressed first stream. Following the sequences b5-b7, symbols b5, b6 and b7 are received from the second stream after compression. Therefore, the subsequent stream 1140 after decompression has symbol b6 (illustrated with reference numeral 1141) from the first stream after compression placed right after symbol b5 from the second stream after compression; Additionally, the correct ordering is ensured, as shown by symbol b7 (illustrated by reference numeral 1142) from the first compressed stream being placed right after symbol b6 from the compressed second stream. Be prepared.

In hardware implementations using FPGAs (or ASICs), available memory is limited, so reverse pointer technology is used to efficiently store strings of multiple lengths (multi-symbol strings). Therefore, in order to ensure decompression, it is necessary to create inverse structures for multiple dictionaries during the compression stage discussed so far, for example with reference to Table 2.

FIG. 12 is a flowchart illustrating a method of creating an inverse structure for decompression, according to an exemplary embodiment. In general, four decoding processes are required to create the inverse structure, but each decoding process for each output symbol (byte) after decoding may be considered one operation. Each operation consists of: (i) reading a compressed symbol of an uninterrupted compressed output stream and emitting an uncompressed symbol represented by the compressed symbol; or (ii) When represented by a multi-symbol string, it involves either emitting the individual symbols in the multi-symbol string one by one in the correct order until the entire string is written out.

Referring to FIG. 12, in step S1201, an instance of a memory structure is created for each incoming wideword input symbol. Examples of instances of memory structures are shown in Table 3A below. Table 3A is a reverse lookup of the compressed dictionary for each input dictionary Di, which associates a 1-byte basic value (eg, a value from 0 to 255) with an appropriate character code value and reverse pointer. Note that the reverse pointer for bytes 0 to 255 is a NULL entry, indicating that these bytes are always the first expected byte (or character) in a multi-symbol string. . Therefore, Table 3A shows only the first possible character of all possible multi-symbol strings that may be formed when decompressing the compressed output stream.

In step S1202, the first arriving symbol reordering process described above is used to iteratively read character codes for separate input streams for each dictionary from the uninterrupted compressed output stream to create Table 3B.

Referring to the example of FIG. 9, compressed codes are provided in a continuous compressed output stream 930 for both the first input stream 911 and the second input stream 912. In this stream of codes, the compressed code is determined by the classification of Table 3B for each of the first input stream 911 and the second input stream 912 (and thus each of the first dictionary D1 and the second dictionary D2). added to the copy. For efficiency, as many operations as there are input streams can be performed in parallel. In FIG. 9, since there are two input streams, two operations can be performed simultaneously and in parallel.

A more detailed example regarding a single input stream (first input stream) will be described below to show how to read the final uninterrupted compressed stream and how to decompress the compressed code. . A portion of the first input stream of the final uninterrupted compressed stream after combined interleaving includes the compressed symbols for the original input stream using the first dictionary (D1). As an example, the first input stream includes the symbol (byte) "cacatcat", which in this example can be compressed into the compressed code "99, 97, 256, 116, 258". As mentioned above, Table 3A is not needed in memory because known ASCII tables can be used to convert characters from single byte values. Therefore, for example, according to the ASCII table, "c"=99, "a"=97, and "t"=116. Since the codes 256 and 258 after compression have values greater than 255, they are multi-symbol strings and are stored in Table 3B. The compressed codes may be iteratively obtained for the first input stream from the uninterrupted compressed output stream, while for the corresponding compressed second input stream, another instance of Table 3B (Fig. (not shown), the same operations are performed in parallel. Additionally, the process uses a second dictionary (D2) to create the data necessary to decode the second input stream.

For the first input stream of this example, the iterative search process of step 1202 includes first reading the compressed code 99 of the compressed output code, and furthermore, after 255 the next available It includes adding a reverse pointer value of 99 to Table 3B of locations (addr) (in the illustrated example, location addr=256). Next, the character code "c" at addr=99 of code 99 after compression is searched and stored at addr=256 of code 256 after compression.

This process continues for other compressed codes. That is, the iterative search process involves reading the compressed code 97 and adding the reverse pointer value 97 to Table 3B at the next available location addr=257 (next to addr=256). It further includes searching for the character code "a" with addr=97 and storing it in addr=257. This process then involves reading the compressed code 256, adding the reverse pointer value 256 to table 3B at the next available location addr=258, and adding the character "c" at addr=256. It also includes retrieving the code and storing it at addr=258. Note that in this way addr=258 has a reverse pointer value greater than 255, in which case the next operation is a new compression on the first input stream, as explained below. It does not read the subsequent code, but follows the reverse pointer to determine the action to take in the next operation on the first input stream. This process then includes reading the compressed code 116, adding the reverse pointer value 116 to Table 3B at the next available location addr=259, and the character code for addr=116 as "t". It also includes searching for and storing in addr=259.

Step 1203 forms a decompressed intermediate output stream by iteratively following the inverse pointer of each compressed code of the uninterrupted compressed output stream for the first input stream and the first dictionary. do. The intermediate output stream after decompression can be stored in a temporary buffer. In this discussion, Table 3B can be viewed as two single-address, dual-port memory structures stored in BRAM or URAM memory on an FPGA, or dual-port SRAM on an ASIC. The output of each operation is one character.

As a result of the iterative process performed on the first input stream, the uncompressed output of each symbol string can be determined by following the chain of reverse pointers until a NULL entry is reached as a reverse pointer, in which case the NULL An entry indicates the beginning of a multi-symbol string. While traversing the reverse pointer, the length of each multi-symbol string after decoding is recorded in a separate memory array L, which may be a third BRAM or a "distributed memory" of an FPGA; In this case, the length of the character string is recorded in the memory array L[0], the length of the first character string, and the length of the second character string in L[1]. One character code is emitted for each action. By following the reverse pointer in this manner, the multi-symbol character string is written out to the temporary queue in reverse order, and is reversed in step S1204, which will be described later.

In this example, the first compressed code that decompresses the compressed code "99, 97, 256, 116, 258" is the compressed code 99. Looking at Table 3A, location addr=99 indicates that the reverse pointer is NULL and the character code is "c". Since this is a one-character code, the length of the character string is L[0]=1. Since the character code "c" is output, the first input stream and the temporary output stream of the first dictionary will therefore contain "c".

The compressed code to be decompressed next is the compressed code 97. Looking at Table 3A, location addr=97 indicates that the reverse pointer is NULL and the character code is "a". The length of the character string is L[1]=1. Since the character code "a" is output, the first input stream and the temporary output stream of the first dictionary now include "ca".

The compressed code to be decompressed next is the compressed code 256. Since addr=256 is greater than the final address (addr=255) in Table 3A, Table 3B is used. Looking at Table 3B, location addr=256 indicates that the reverse pointer is non-NULL and has a value of 99. Therefore, the first character code of address value i+1 (ie, 256+1=257) is read and output. Location addr=257 indicates that the first character code is "a". The reverse pointer value 99 for location addr=256 is followed by addr=99, which indicates that the reverse pointer is NULL and the second character code is "c". Therefore, by tracing the inverse pointer of the compressed code 256 until it reaches a NULL entry, the first character code "a" and the second character code "c" are output as the multi-symbol character string "ac". It turns out. Since there are two character codes, the length of this character string is L[2]=2. Note that the next compressed code for the first input is read from the unbroken compressed output stream in the next iteration until the two character codes of compressed code 256 are output together. Not served. The first input stream and temporary output stream of the first dictionary now contain "caac".

The compressed code to be decompressed next is the compressed code 116. Looking at Table 3A, location addr=116 indicates that the reverse pointer is NULL and the character code is "t". The length of the character string is L[3]=1. Since the character code "t" is output, "caact" is now included in the first input stream and the temporary output stream of the first dictionary D1.

The next compressed code to be decompressed is the compressed code 258. Again, addr=258 is greater than the final address in Table 3A, so Table 3B is used. Looking at Table 3B, location addr=258 indicates that the reverse pointer is non-NULL and has a value of 256. Therefore, the first character code of address value i+1 (ie, 258+1=259) is read and output. Location addr=259 indicates that the first character code is "t". A reverse pointer value of 256 for location address 258 follows addr=256, which is also non-NULL (as described above). Therefore, the second character code of address value i+1 (ie, 256+1=257) is read and output. Location addr=257 indicates that the second character code is "a". The reverse pointer value 99 of addr=256 is followed by addr=99, and in this case, the reverse pointer is NULL and the character code is "c", which is the third character code. Therefore, by tracing the inverse pointer of the compressed code 258 until it reaches the NULL entry, the first character code "t", the second character code "a", and the third character code "c" are converted to the multi-symbol Output as the character string "tac". Since there are three character codes, the length of this character string is L[4]=3. The first input stream and temporary output stream of the first dictionary now contain "caacttac". Also, the respective sub-lengths are L[0]=1, L[1]=1, L[2]=2, L[3]=1, and L[4]=3. . With this information, the strings "c", "a", "ac", "t", and "tac" can be reversed to obtain the correct order.

In step S1204, a decompressed stream of the first input stream and the first dictionary is formed by reversing the order of character codes of the multi-symbol string in the intermediate output stream after decompression from the temporary buffer. . For example, in the code 256 after compression, "ac" becomes "ca", and in the code 258 after compression, "tac" becomes "cat". This is because the hardware structure holds a reverse pointer, and therefore compressed symbols that encode multiple bytes must rearrange the reversed strings. In this example, a symbol encoding three original characters, such as ``tac'', is converted into the correct string ``c'', then ``a'', then ``t'' over three cycles of operation in the opposite direction. is released as ``cat'' is obtained. Therefore, in step 1204, the multi-symbol string in the temporary buffer is repeatedly reversed to arrive at "c", "a", "ca", "t", and "cat", and the output Form an uncompressed stream. The multi-symbol string is reverse ordered according to the length L[n] of each value greater than one.

In hardware (eg, FPGA or ASIC), one character is emitted per operation. Therefore, from an operational standpoint, step S1201 may be executed one operation ahead of the operation corresponding to step S1203. That is, it is necessary to attempt the operation corresponding to step S1203 after the calculation in step S1201 is completed. Note that each time the reverse pointer is followed in step S1203, the stored length for this multi-symbol string is incremented. This length information is applied in step S1204.

Although updating and storing the length value requires one operation, it is also possible to update the length value simultaneously with other operations in the entire calculation performed in step S1203. In any case, until the last character of the reversed multi-symbol string is calculated in step S1203, the information in the length array is used to calculate the first reverse order of the multi-symbol string. It is not possible to emit characters that are not specified. Therefore, in step S1204, at least the "Llongest" operation occurs after the equivalent operation in step S1203. Here, "Llongest" is a character string with the longest length L.

Step S1202 is executed immediately before step 1203 in a pipeline that overlaps with this step. That is, step 1203 calculates input stream [n-1], and step 1202 calculates input stream [n]. That is, after calculating all codes after compression in step 1202, the process moves to step 1203 to calculate the same codes after compression. Step 1204 is redundant, but delayed by several operations determined by the length of the longest multi-symbol string.

In hardware, the model used when decompressing data scans the capture buffer and searches the data for points of interest. Search time is not as time-critical as capture time, so each decompression operation may take one or more clock cycles, if desired. Therefore, constraints on the time taken for decompression may be more relaxed than for compression.

When processing multiple input streams in parallel, the length of the compressed character string needs to be longer than 1 because the compressed character string becomes a multi-symbol character string with a compressed code exceeding 255. Similarly, when following a reverse pointer, a value greater than 255 means that at least one more character must be read. Even if the string is not fully decoded yet, if the compressed code is found to be a multi-symbol string, the next operation determines that the next compressed code in the input stream should not be read. sufficient information can be obtained. Instead, on the next operation that reads the next wideword input, rather than reading the next compressed symbol of the same wideword input, the inverse pointer is followed to determine the next character to be output during the next operation. get. That is, once a multi-symbol string is created, it reads the unbroken compressed and interleaved output stream of compressed codes created from multiple inputs and takes them into account when addressing multiple dictionaries Di. There will be one or more NoOps required.

In summary, in Table 3B, a reverse pointer with a value between 0 and 255 indicates that the next symbol is the last of the multi-symbol string, and the process also It is necessary to proceed to the code after compression. However, a reverse pointer with a value greater than 255 indicates that there is at least one subsequent reverse pointer. After the next iteration, if the inverse pointer of the previous step in the input stream is not NULL, then another NoOp has been generated during compression, so the next compression in the output stream after uninterrupted compression with respect to the input stream The code should not be read. Therefore, instead of reading the next compressed code, the inverse pointer is traced again to extract the character code to be output. Similarly, if the subsequent reverse pointer is also non-NULL, it indicates that there is another character in the multi-symbol string to be output. However, if the reverse pointer is NULL, all combined symbols in the multi-symbol string have been extracted and the process needs to proceed to the next input compressed code in the current input stream and dictionary.

When word-sized operations are executed in parallel, each operation 'i' reads the next character code for the next input stream, as long as the previous compressed code of the corresponding input stream is represented by a single character code. It will be done. Otherwise, if the previous character code of the input stream is a multi-symbol string, the next Skip reading the character code in favor of either the character code or skip to the next input stream; again, the character code is read for each input, if necessary. Or, a multi-symbol string is output for each input and dictionary. Note that the first character code in each input stream/dictionary combination i=0 always represents a single character. In this way, the character codes of the compressed output stream are read in a round-robin manner.

In the examples of FIGS. 10 and 11, the word size of the wide word is 2, so repetition is performed in a pair-wise manner. 13A-13C similarly illustrate an example of ordering the symbols of multiple wideword inputs for compression, in accordance with a representative embodiment, where the wideword size is two.

Referring to FIG. 13A, the serial stream 1320 to be compressed includes 16 symbols (bytes), with two wide words including the symbol "ccbaccbactbccadt". The serial stream 1320 is arranged such that every other symbol is assigned to one of the two widewords, as indicated by the different shading in the serial stream of symbols designated by reference numeral 1330. Therefore, it includes a first input stream 1331 with the symbol "cbcbcbcd" for the first dictionary (D1) and a second input stream 1332 with the symbol "cacatcat" for the second dictionary (D2). All other symbols are grouped together for compression into separate input streams. Note that the second input stream 1332 is the same as the exemplary first input stream discussed above with reference to Tables 3A and 3B.

In accordance with the compression embodiments described above, parallel compression is performed on the first input stream 1331 and the second input stream 1332 in eight clock cycles denoted cc1 to cc8. First input stream 1331 and second input stream 1332 may be compressed using, for example, known ASCII tables. Compressing the first input stream 1331 results in a compressed first stream 1341 (0 after compression), and compressing the second input stream 1332 results in a compressed second stream 1342 (1 after compression). is obtained. In the illustrated example, the first stream 1341 after compression includes the compression codes "99, 98, NoOp, 256, NoOp, NoOp, 258, 100", and the second stream 1342 after compression includes the compression codes "99, 98, NoOp, 258, 100". 97, NoOp, 256, 116, NoOp, NoOp, 258'' (described above).

Referring to FIG. 13B, the first stream 1341 and the second stream 1342 after compression are reordered according to the reordering of the first arriving symbols and stored in the temporary buffer, so that the first stream 1341 and the second stream 1342 after compression are stored in the temporary buffer, so that the first stream 1341 and the second stream 1342 after compression are stored in the temporary buffer, so that the first stream 1341 and the second stream 1342 after compression are reordered according to the reordering of the first arriving symbols and stored in the temporary buffer. The string is relocated to the position of the first symbol within the group of symbols. In particular, in the compressed first stream 1341, the compressed multi-symbol string represented by the symbol 256 is moved from the fourth position to the third position, and the NoOp entry is shifted one position to the right. , by moving the compressed code 258 from the seventh position to the fifth position and shifting the NoOp entry by one position to the right, the reordered compressed first stream 1341' (post-compressed 0') is obtained. In the compressed second stream 1342, the compressed multi-symbol string represented by the symbol 256 is moved from the fourth position to the third position, the NoOp entry is shifted one place to the right, and the compressed By moving the latter code 258 from the eighth position to the sixth position and shifting the NoOp entry one place to the right, the reordered compressed second stream 1342' (compressed 1' ) is obtained. Notably, the compressed codes 256 and 258 of the compressed second stream 1342 include different character codes than the compressed codes 256 and 258 of the compressed first stream 1341.

By alternately inputting symbols from the rearranged compressed first stream 1341' and compressed second stream 1342', a final compressed output stream 1350 is formed. NoOp entries are excluded from this process, so the compressed output stream 1350 is seamless. Therefore, the compressed code 258 from the reordered compressed first stream 1341' immediately follows the compressed code 256 from the reordered compressed second stream 1342' and is reordered. The compressed code 258 from the permuted compressed second stream 1342' immediately follows the compressed code 116 from the permuted compressed second stream 1342', and further The compressed code 100 from the reordered compressed first stream 1341' immediately follows the compressed code 258 from the reordered compressed second stream 1342'.

Referring to FIG. 13C, in accordance with a representative embodiment, decompression is performed on the compressed output stream 1350 to provide a decompressed stream 1360, which is shown in FIG. 13A. Matches the original serial stream 1320. Decompression is performed in an iterative operation from left to right in the configuration shown. The compressed output stream 1350 is shown at the top of FIG. 13C, where, for convenience, blocks representing symbols and multi-symbol strings with corresponding addresses have been separated. As discussed above, decompression is performed in a series of iterative decoding operations, using each inverse pointer to determine the corresponding character code(s), and decompression A later intermediate stream 1355 may be formed and stored in a temporary buffer. The final decompressed stream 1360 is formed by reversing the order of the character codes of each multi-symbol string in the compressed output stream 1350.

For convenience, the entire decompressed intermediate stream 1355 of FIG. 13C is shown to illustrate the overall decoding process and the order of character codes after decoding. However, the entire decompressed intermediate stream 1355 is not necessarily formed before proceeding to the next step of inputting the decoded character codes into the final decompressed stream 1360. That is, in some embodiments, when constructing the decompressed intermediate stream 1355, the decoded character codes of the decompressed intermediate stream 1355 may be presented piecewise into the decompressed final stream 1360. , which reduces the size of the temporary buffer required for intermediate decompression. For example, each decoded character code can be input from the decompressed intermediate stream 1355 to the decompressed final stream 1360 if the corresponding reverse pointer is NULL. As mentioned above, arriving at a null inverse pointer requires multiple decoding steps of the multi-symbol string (and reversal of the order when entering the final stream 1360 after decompression). be.

In the illustrated example, the compressed code 99 from the rearranged compressed first stream 1341' has a reverse pointer to NULL, so the character code is placed at the beginning position of the decompressed intermediate stream 1355. "c" is output. Since the compressed code 99 from the rearranged compressed second stream 1342' has a reverse pointer to NULL, the character code "c" is output at the next position of the decompressed intermediate stream 1355. be done. Since the compressed code 98 from the rearranged compressed first stream 1341' has a reverse pointer to NULL, the character code "b" is output at the next position of the decompressed intermediate stream 1355. be done. Since the compressed code 97 from the rearranged compressed second stream 1342' has a reverse pointer to NULL, the character code "a" is output at the next position of the decompressed intermediate stream 1355. be done. The length of each of these character strings is expressed as L=1.

The compressed code 256 from the reordered compressed first stream 1341' provides the multi-symbol string "bc", and the compressed code 256 includes the character code "b" and the character It has a reverse pointer to 99 whose code is "c" and a reverse pointer to NULL. Therefore, over the next two operations with the reordered compressed first stream 1341', the character code "b" is output in the next position of the decompressed intermediate stream 1360, and the character code "c" is output to the position immediately after skipping the next position. (As described below, the order of the character codes "b" and "c" is then swapped when forming the decompressed stream 1360). Similarly, the compressed code 256 from the reordered compressed second stream 1342' provides the multi-symbol string "ac", where the compressed code 256 is the character code It has a reverse pointer to "a", a reverse pointer to 99 whose character code is "c", and a reverse pointer to NULL. Therefore, over the next two operations with the reordered compressed second stream 1342', the character code "a" is changed to the compressed code of the reordered compressed first stream 1341'. 256, the character code "b" is output to the next position of the intermediate stream 1355 after decompression, and the character code "c" is output to the position immediately after skipping the next position. . The length of each of these character strings is expressed as L=2. Note that the string length value L can be used to determine when the decoded and compressed symbols may be input into the final decompressed stream 1360.

The compressed code 258 from the reordered compressed first stream 1341' then provides the multi-symbol string "cbc", where the compressed code 258 is the character code "c", a reverse pointer to 256 whose character code is "b", a reverse pointer to 99 whose character code is "c", and a reverse pointer to NULL. Therefore, over the next three operations with the reordered compressed first stream 1341', the character code "c" is output to the next position of the decompressed intermediate stream 1355, and the character code "c" is output to the next position of the decompressed intermediate stream 1355, "b" is output to the position immediately after the next position is skipped, and furthermore, the character code "c" is output to the position immediately after the next position is skipped. On the other hand, the compressed code 116 from the reordered compressed second stream 1342' has a reverse pointer to NULL, so the character code "t" first appears from the compressed code 258. It is output to the position of the intermediate stream 1355 after decompression following the character code "c". The length of the character string with code 258 after compression is shown as L=3, and the length of the character string with code 116 after compression is shown as L=1.

Finally, the compressed code 258 from the reordered compressed second stream 1342' provides the multi-symbol string "tac", and the compressed code 258 has the character code "t". , a reverse pointer to 256 whose character code is "a", a reverse pointer to 99 whose character code is "c", and a reverse pointer to NULL. Therefore, over the next three operations with the reordered compressed second stream 1342', the character code "t" is changed to the compressed code of the reordered compressed first stream 1341'. 258, the character code "b" is output to the next position of the intermediate stream 1355 after decompression, the character code "a" is output to the position immediately after skipping to the next position, and the character code "a" is output to the position immediately after skipping to the next position, and The code "c" is output to the position immediately after the next position is skipped. On the other hand, since the compressed code 100 from the rearranged compressed first stream 1341' has a reverse pointer to NULL, the character code "d" is the character code "d" from the compressed code 258. a'' is output to the next position of the decompressed intermediate stream 1355. The length of the character string with code 258 after compression is shown as L=3, and the length of the character string with code 100 after compression is shown as L=1.

Decompressed stream 1360 is formed from decompressed intermediate stream 1355 by reversing the order of the respective character codes within the multi-symbol string. In the illustrated example, the multi-symbol character string of the rearranged and compressed first stream 1341' includes a compressed code 256 regarding the character code "bc" and a compressed code 258 regarding the character code "cbc". Furthermore, the multi-symbol character string of the rearranged and compressed second stream 1342' includes a compressed code 256 regarding the character code "ac" and a compressed code 258 regarding the character code "tac". including. As seen in FIG. 13C, the order of the character code "bc" from the compressed code 256 of the reordered compressed first stream 1341' is the same as that of "c" in the decompressed stream 1360. It is later received in the reverse order (reverse order) as "b". The order of the character codes "ac" from the compressed code 256 of the rearranged compressed second stream 1342' is received in the reverse order of "c" followed by "a" in the decompressed stream 1360. be done. The order of the character code "cbc" from the compressed code 258 of the rearranged compressed first stream 1341' is such that in the decompressed stream 1360, "c" is followed by "b", followed by " c" in reverse order. The order of the character code "tac" from the compressed code 258 of the rearranged compressed second stream 1342' is such that in the decompressed stream 1360, "c" is followed by "a", followed by " t'' in reverse order.

Once complete, the resulting decompressed stream 1360 will be the same as the original serial stream 1320 shown in FIG. 13A. In an alternative embodiment, the compressed symbols originating from the reordered compressed first stream 1341' are transferred to the first temporary output stream (characters of the multi-symbol string) stored in the first temporary buffer. The compressed codes originating from the reordered compressed second stream 1342' are then decompressed into a second temporary Decompress as a buffered second temporary output stream (which may or may not contain the character codes of the multi-symbol string in reverse order). The decompressed stream 1360 can then be formed by alternately inputting symbols from the first temporary output stream and the second temporary output stream.

In an alternative embodiment, instead of a buffering step in which each NoOp entry is replaced with the next available multi-symbol string, this buffering step is such that all NoOp entries are removed before putting together the compressed stream. , involves a process in which the multi-symbol string is shifted to the location of the NoOp entry by simply deleting each NoOp entry. That is, the value of the multi-symbol moves to the first occurrence of each NoOp operation. This advantageously replaces multiple write operations with a single write operation corresponding to each entry of the NoOp.

FIG. 14 illustrates symbols of wideword data reordered for input for decompression, according to an exemplary embodiment. Referring to FIG. 14, it is assumed that compressing the first input stream 1411 results in a compressed multi-symbol string corresponding to the two original arriving symbols b5 and b6. Conventionally, for example, as shown in the compressed first stream 821 of FIG. Multi-symbol string b5/b6 is placed at the original position of symbol b6 in the stream. However, in the embodiment shown in FIG. 14, this compression operation deletes the NoOp entry from the compressed first stream 1421 corresponding to the first input stream 1411, and further converts the multi-symbol string b5/b6 into It is shifted to the position of the deleted NoOp entry (the original position of symbol b5). By rearranging the "shifted symbols" and storing the original size of the input stream, the original order of symbols b5 and b6 can be obtained from the compressed output stream 1430 stored in the capture buffer. Sufficient information is retained to restore the data. When the combined multi-symbol string b5/b6 is decoded, the multi-symbol string b5/b6 is decoded from the original two with respect to the first input stream 1411, which is also known to belong to the first dictionary D1. The obtained data code can be queried as to whether it corresponds to uncompressed symbols b5 and b6. Therefore, the order is preserved.

Specifically, FIG. 14 shows a first input stream 1411 (input stream 0) and a second input stream 1412 (input stream 1) of wideword data, which are provided below for compression. . The first input stream 1411 and the second input stream 1412 may correspond to the first input stream 631 and the second input stream 632, respectively, discussed above with reference to FIG. are different. FIG. 14 shows the first stream 1421 after compression (0 after compression) calculated for the first input stream 1411 and rearranged (after shifting) according to the present embodiment, and the calculated value for the second input stream 1412. A second stream 1422 (after compression 1) is also shown after compression. The compressed first stream 1421 and the second compressed stream 1422 correspond to the order of operations at intermediate steps during the compression process before the data is written to the capture buffer as a continuous compressed output stream 1430. Subsequent decompression is performed on the compressed output stream 1430 according to known decompression algorithms. The final decompressed stream 1440 shows correctly ordered decompressed data despite the NoOp entries generated during compression of the first input stream 1411.

According to the illustrated embodiment, the uninterrupted compressed output stream 1430 for wide words is such that consecutive compressed symbols from the alternating compressed first stream 1421 and the compressed second stream 1422 are Written during compression so that they follow each other without entries. When one or more symbols are compressed into a multi-symbol string, the compressed symbols are temporarily buffered and then stored in the compressed state as if they had been created in the original position of the NoOp entry. is emitted to the previous NoOp entry position so that the symbol appears. If the original arriving symbols cannot be compressed, they are each ejected into the correct location during correct operation, or shifted by the same number of entries as the preceding multi-symbol string was shifted.

In the exemplary dual-wideword system described herein (for ease of explanation), the compressed output always pairs as the first input stream 1411 and then the second input stream 1412. released as a unit. The compressed first stream 1421 corresponding to the first input stream 1411 includes the compressed multi-symbol string b5/b6 written at the corresponding position of symbol b5, and at this position, the NoOp entry (e.g. The compressed first stream 821 in FIG. 8) is deleted, and the compressed multi-symbol character string b5/b6 is further shifted to the position of symbol b5. The compressed second stream 1422 includes all the symbols of the second input stream 1412.

The compressed output stream 1430 receives symbols alternating between a compressed first stream 1421 and a compressed second stream 1422. Of note, there are cases where one input stream compresses better than another, resulting in a compressed stream. For example, compression of the first input stream 1411 is better than compression of the second input stream 1412, such that the first stream 1421 after compression is shorter than the second stream 1422 after compression. Become. In this case, the compression from the long stream towards the end of the compressed stream such that symbols b6 and b7 from the compressed second stream 1422 are adjacent to each other at the end of the compressed output stream 1430, etc. Later symbols will be placed together. Therefore, the number of compressed symbols of each compressed stream is tracked during decompression, and furthermore, when the number reaches the original size of the corresponding decompressed input stream of the compressed stream, the corresponding For the remainder of the wideword decompression, the compressed stream is skipped.

In the illustrated example, the original size of each of the first input stream 1411 corresponding to the compressed first stream 1421 and the second input stream 1412 corresponding to the second stream 1422 is 7. This value is the same for all compressed streams since the size of the original input stream is chosen to fit exactly within the wideword stream. In the illustrated example, the original input stream is selected to be 14, so the first input stream 1411 and the second input stream 1412 (each having a size of 7) have a total of 14. Generally, the size n of the page is chosen such that n%wide_word=0 (ie, the size of the page is divisible by the wideword). Upon decompression, as discussed below, the compressed first stream 1421 and/or second stream 1422 (i.e., first stream 1421 and/or second stream 1422) is As soon as a decompression value of 1 is reached, it is known that the compressed stream is completely decompressed.

With respect to receiving symbols b1 from the compressed first stream 1421 and the compressed second stream 1422 alternately, the compressed output stream 1430 receives the symbols b1 from the compressed first stream 1421 and the symbols b1 from the compressed first stream 1421. The symbol b1 is received from the second stream 1422, the symbol b2 is received from the compressed first stream 1421, the symbol b2 is received from the compressed second stream 1422, and so on. This post-interleaving process includes receiving multi-symbol string b5/b6 from the compressed first stream 1421 after receiving symbol b4 from the compressed second stream 1422; 2; receiving symbol b7 from compressed first stream 1421; and further receiving symbol b7 from compressed second stream 1422. Proceed as follows. In the illustrated order, it is possible to recover the data in each dictionary in its original order, as seen in the decompressed stream 1440 (again, indicated by circle 1435), and the data from multiple input streams as widewords. can be restored. In particular, symbol b6 (illustrated with reference numeral 1441) from the compressed first stream 1421 is placed right after symbol b5 from the compressed second stream 1422.

By rearranging (deinterleaving) the "symbols after shifting," it is possible to maintain two pieces of prerequisite information required to reconstruct data in the correct order. First, in the illustrated example, we know that the multi-symbol string b5/b6 arrived at the location of symbol b5 in the first input stream 1411 rather than at the location of symbol b6, and therefore 1 dictionary D1. Second, by examining the obtained data regarding the multi-symbol string b5/b6, it is found that the length of the final uncompressed string exceeds one symbol. Therefore, when decoding the compressed multi-symbol string b5/b6 to obtain, for example, a decompressed stream 1440, when the correct timing for the write operation comes, symbol b5 is written out first, then symbol b6 is written out. I will write it out. In this way, symbols b5 and b6 are both written to the correct position in the final stream 1440 after decompression. Furthermore, since the final length of the multi-symbol string b5/b6 is known to be two uncompressed symbols, the dictionary to which the next code of the compressed output stream 1430 belongs can be calculated. In particular, in hardware implementations using FPGAs (or ASICs), symbols are reversed in order due to the reverse pointer technique discussed below.

15A-15C similarly illustrate an example of ordering symbols of multiple wideword inputs for decompression, in accordance with a representative embodiment, where the wideword size is two. In particular, FIGS. 15A-15C illustrate in more detail the steps of deleting a NoOp entry and respectively shifting subsequent multi-symbol strings to the position of the deleted NoOp entry.

Referring to FIG. 15A, the serial stream 1520 to be compressed includes 16 symbols (bytes), with two wide words including the symbol "ccbaccbactbccadt". The serial stream 1520 is arranged such that every other symbol is assigned to one of the two widewords, as indicated by the different shading in the serial stream of symbols designated by the reference numeral 1530. Therefore, it includes a first input stream 1531 with the symbol "cbcbcbcd" for the first dictionary (D1) and a second input stream 1532 with the symbol "cacatcat" for the second dictionary (D2). All other symbols are grouped together for compression into separate input streams. Note that the second input stream 1532 is the same as the exemplary first input stream discussed above with reference to Tables 3A and 3B above.

In accordance with the compression embodiments described above, parallel compression is performed on the first input stream 1531 and the second input stream 1532 in eight clock cycles denoted cc1 to cc8. First input stream 1531 and second input stream 1532 may be compressed using, for example, known ASCII tables. Compressing the first input stream 1531 results in a compressed first stream 1541 (0 after compression), and compressing the second input stream 1532 results in a compressed second stream 1542 (1 after compression). is obtained. In the illustrated example, the first stream 1541 after compression includes the compression codes "99, 98, NoOp, 256, NoOp, NoOp, 258, 100", and the second stream 1542 after compression includes the compression codes "99, 98, NoOp, 258, 100". 97, NoOp, 256, 116, NoOp, NoOp, 258'' (described above).

Referring to FIG. 15B, the first stream 1541 and the second stream 1542 after compression are shifted according to the rearrangement of the symbols after the shift, and may or may not be stored in the temporary buffer. , the compressed code representing the multi-symbol string is shifted into the corresponding NoOp entry created during compression. In particular, in the compressed first stream 1541, the NoOp entry in the third position is deleted, and the multi-symbol string represented by the compressed code 256 is shifted from the fourth position to the third position. Also, the NoOp entries in the fifth and sixth positions are deleted, and the compressed code 258 is transferred from the seventh position to the fifth position (i.e., the two adjacent NoOp entries before the compressed code 258). the first NoOp entry). The result is a reordered (shifted) compressed first stream 1541' (0' after compression). In the compressed second stream 1542, the NoOp entry is removed from the third position and the compressed multi-symbol string, represented by the symbol 256, is shifted from the fourth position to the third position and the NoOp entry is removed from the third position. The NoOp entry in the 6th position and the 7th position are deleted, and the compressed code 258 is further shifted from the 8th position to the 6th position, so that the compressed code 258 is rearranged (shifted). A second stream 1542' (1' after compression) is provided. This may also be referred to as a buffering step, regardless of whether the reordered compressed first stream 1541' and second stream 1542' are stored in a buffer. Of note, the compressed codes 256 and 258 of the compressed second stream 1542 include different character codes than the compressed codes 256 and 258 of the compressed first stream 1541; , which is an important reason to keep track of the input stream from which these compressed streams originate.

By alternately inputting symbols in order from the rearranged (shifted) compressed first stream 1541' and the compressed second stream 1542', the final compressed output stream 1550 is generated. It is formed. Since the NoOp entries were previously removed, the compressed output stream 1550 is continuous. Therefore, the compressed code 256 from the reordered compressed first stream 1541' immediately follows the compressed code 97 from the reordered compressed second stream 1542', and The compressed code 256 from the permuted compressed second stream 1542' immediately follows the compressed code 256 from the permuted compressed first stream 1541', and The compressed code 258 from the compressed first stream 1541' immediately follows the compressed code 256 from the reordered compressed second stream 1542', and further The compressed code 258 from the later second stream 1542' immediately follows the compressed code 100 from the reordered compressed first stream 1541'. Due to the different buffering steps, the final compressed stream 1550 is different from the compressed final output stream 1350 of the embodiment seen in FIG. 13B described above.

15C, in accordance with a representative embodiment, decompression is performed on the compressed output stream 1550 to provide a decompressed stream 1560, where the decompressed stream 1560 is the same as that shown in FIG. 15A. This corresponds to the original serial stream 1520 shown in . Decompression is performed in an iterative operation from left to right in the configuration shown. The compressed output stream 1550 is shown at the top of FIG. 15C, where blocks representing symbols and multi-symbol strings and corresponding addresses and parameters have been separated for convenience. As discussed above, decompression is performed in a series of iterative decoding operations, using each inverse pointer to determine the corresponding character code(s), and after decompression 1555, which may be stored in whole or in part in a temporary buffer. The final decompressed stream 1560 is formed by reversing the order of the character codes of each multi-symbol string in the compressed output stream 1550.

When determining the decompressed intermediate stream 1555, address information and parameters are updated in association with each compressed code. The address information includes the address (adr) of the current compressed code included in the decompressed stream 1560. The parameters include the compressed code length (L), which is the number of compressed symbols in the compressed code, the wideword (w), which is the number of input streams in the wideword, and the current A decompression value (dc) is included that indicates the cumulative number of decompressed symbols from the same input stream at the time of the decompression process when the compressed code is decompressed. The next address of the next compressed code starting from the same input stream is calculated by adding the product of length (L) and wideword (w) to the current address (adr+Lw). The next decompression value for the same input stream is calculated by adding the length (L) to the current decompression value (dc+L).

For convenience, the entire decompressed intermediate stream 1555 of FIG. 15C is shown to illustrate the entire decoding process and the order of character codes after decoding. However, the entire decompressed intermediate stream 1555 is not necessarily formed before proceeding to the next step of inputting the decoded character codes into the decompressed final stream 1560. That is, in some embodiments, when constructing the decompressed intermediate stream 1555, the decoded character codes of the decompressed intermediate stream 1555 may be presented piecewise into the decompressed final stream 1560. , which reduces the size of the temporary buffer required for intermediate decompression. For example, each decoded character code can be input from the decompressed intermediate stream 1555 to the decompressed final stream 1560 if the corresponding reverse pointer is NULL. As mentioned above, arriving at a null reverse pointer requires multiple decoding steps of the multi-symbol string (and reversal of the order when entering the final stream 1560 after decompression).

Furthermore, in decompression, it is not necessary to partially output each of the rearranged compressed first stream 1541' and second stream 1542'. Decompression uses addresses to keep track of the position in the decompressed stream 1560 where the decompressed string is ultimately output, reducing the amount of buffer memory required; Furthermore, as a separately formed interleaving step, the intermediate stream 1555 after decompression may be effectively deleted. Since the addresses are tracked in an array of wideword size (eg, 2 in this example) and each stream is effectively decompressed independently, the decompression process can be performed in parallel. The final positions of the reordered compressed first stream 1541' and second stream 1542' are known when they are decoded, so that the compressed output stream 1550 is not yet fully decoded. The first few decoded characters of the final stream 1560 after decompression can be output even when not. Multi-symbol strings need to be temporarily stored during decompression to reverse the order of decoded character codes that should be provided to the decompressed stream 1560, and then used as needed. The multi-symbol string can be deleted from storage accordingly.

In particular, referring to the illustrated example, the compressed code 99 from the reordered compressed first stream 1541' has a reverse pointer to NULL, so that the first compressed code 99 of the decompressed intermediate stream 1555 At the position, the character code "c" is output together with the corresponding address information and parameters. As shown in the figure, the address of code 99 after compression is 0 (adr[0]=0) since this is the first symbol after decompression of stream 1560 after compression; The length of code 99 is 1 (L=1) since this corresponds to 1 symbol after compression, and furthermore, the decompression value of code 99 after compression is such that no symbols have been decompressed so far. Therefore, 0 (dc[0]=0). The next address of the next decompressed symbol starting from the first input stream 1531 is 2, which is equal to the length of the compressed code 99 (L) and the wideword size (w). The product is added to the current address of code 99 after compression (adr[0]+L*w=0+(1*2)=2). Also, the next decompression value (dc), which indicates the cumulative number of symbols decompressed from the first input stream 1531 so far, is 1, and this value is equal to the length of the current decompression value of code 99. It is obtained by adding the values of (L) (dc[0]+L=0+1=1). Compare the following decompression value with the total number of symbols (8) in the original first input stream 1511 to determine whether the reordered compressed first stream 1541' is completely decompressed. do. In this case, the next decompression value is 1, and since 1 is less than 8, the decompression of the compressed first stream 1541' does not stop here.

Since the compressed code 99 from the rearranged compressed second stream 1542' has a reverse pointer to NULL, the character code "c" is placed in the next position of the decompressed intermediate stream 1555. , the corresponding address information, and parameters. In other words, the address of code 99 after compression is 1 (adr[1]=1) since this is the second symbol after decompression of stream 1560 after decompression, and the length of code 99 after compression is 1 (adr[1]=1). Since this corresponds to one symbol after compression, it is 1 (L=1), and furthermore, since there is no symbol that has been decompressed so far for the reordered compressed second stream 1542'. , the decompression value 99 of the code after compression is 0 (dc[1]=0). The next address of the next decompressed symbol starting from the second input stream 1532 is 3, which is equal to the length of the compressed code 99 (L) and the wideword size (w). The product is added to the current address of code 99 after compression (adr[1]+L*w=1+(1*2)=3). The next decompression value (dc), which indicates the cumulative number of symbols decompressed from the second input stream 1532, is 1, which is equal to the current code 99 decompression value plus the length (L) value. (dc[1]+L=0+1=1). Compare the following decompression value with the total number of symbols (8) in the original second input stream 1512 to determine whether the reordered compressed second stream 1542' is completely decompressed. do. In this case, the next decompression value is 1, and since 1 is less than 8, the decompression of the compressed second stream 1542' does not stop here.

Since the compressed code 98 from the rearranged compressed first stream 1541' has a reverse pointer to NULL, the character code "b" is output at the next position of the decompressed intermediate stream 1555. be done. The corresponding address information includes adr[0]=2 (which was previously updated with the preceding compressed code 99 from the reordered compressed first stream 1541'); And the corresponding parameters are L=1 and dc[0]=1 (which was previously updated with the preceding compressed code 99 from the reordered compressed first stream 1541'). ). After that, address adr[0] is updated with the next value, and becomes adr[0]+Lw=2+(1*2)=4. The value dc[0] after decompression is also updated with the next value, dc[0]+L=1+1=2, which is less than 8, so the decompression of the first stream 1541' after compression is Do not stop. Similarly, since the compressed code 97 from the rearranged compressed second stream 1542' has a reverse pointer to NULL, the next position of the decompressed intermediate stream 1555 is the character code "a". " is output. The corresponding address information includes adr[1]=3 (which was previously updated with the preceding compressed code 99 from the reordered compressed second stream 1542'); And the corresponding parameters are L=1 and dc[1]=1 (which was previously updated with the preceding compressed code 99 from the reordered compressed second stream 1542'). ). Thereafter, address adr[1] is updated to become adr[1]+Lw=5. The value dc[1] after decompression is also updated with the next value, dc[1]+L=2, but since this is less than 8, the decompression of the second stream 1542' after compression is not stopped. .

The compressed code 256 from the reordered compressed first stream 1541' then provides the multi-symbol string "bc", and the compressed code 256 has the character code "b". , has a reverse pointer to 99 whose character code is "c", and a reverse pointer to NULL. Therefore, when the character codes "b" and "c" are respectively output and then written to the decompressed stream 1560, their positions are reversed. The corresponding address information includes adr[0]=4, which is then updated to 8. The corresponding parameters are L=2 and dc[0]=2, which is then updated to 4. The compressed code 256 includes two character codes (“bc”) from two symbols of the first input stream 1531, so the length (L) is two. Address (adr[0]) is updated to 8 according to adr[0]+Lw=4+(2*2)=8. Update the decompressed value (dc[0]) to 4 according to dc[0]+L=2+2=4, which means that the 4 symbols ("cbcb") from the first input stream 1531 are decoded. will be done. Since 4 is less than 8, the decompression of the reordered compressed first stream 1541' does not stop.

Similarly, the compressed code 256 from the reordered compressed second stream 1542' provides the multi-symbol string "ac", and the compressed code 256 is the character code "a". , a reverse pointer to 99 whose character code is "c", and a reverse pointer to NULL. Therefore, when the character codes "a" and "c" are respectively output and then written to the decompressed stream 1560, their positions are reversed. The corresponding address information includes adr[1]=5, which is updated to 9. The corresponding parameters are L=2 and dc[1]=2, which are updated to 4. Compressed code 256 contains two character codes (“ac”) from two symbols of second input stream 1532, so its length (L) is two. Address (adr[1]) is updated to 9 according to adr[1]+Lw=5+(2*2)=9. Update the decompressed value (dc[1]) to 4 according to dc[1]+L=2+2=4, which means that the 4 symbols ("ccaca") from the second input stream 1532 are decoded. Indicates that the Since 4 is less than 8, decompression of the reordered compressed second stream 1542' does not stop.

The compressed code 258 from the reordered compressed first stream 1541' then provides the multi-symbol string "cbc" and the compressed code 258 has the character code "c". , a reverse pointer to 256 whose character code is "b", a reverse pointer to 99 whose character code is "c", and a reverse pointer to NULL. Therefore, when the character codes "c", "b", and "c" are respectively output and then written to the decompressed stream 1560, their positions are reversed. The corresponding address information includes adr[0]=8, which is then updated to 14, and the corresponding parameters are L=3 and dc[0]=4, which is updated to 7. do. The compressed code 258 contains three character codes (“cbc”) from the three symbols of the first input stream 1531, so the length (L) is three. Update the address to 14 according to adr[0]+Lw=8+(3*2)=14. Update the decompressed value (dc[0]) to 7 according to dc[0]+L=4+3=7, which means that 7 symbols (“cbcbcbc”) from the first input stream 1531 are decoded. Indicates that the Since 7 is less than 8, the decompression of the reordered compressed first stream 1541' does not stop.

Next, since the compressed code 116 from the rearranged compressed second stream 1542' has a reverse pointer to NULL, the character code " t'' is output along with the corresponding address information and parameters. That is, the corresponding address information includes adr[1]=9, which is then updated to 11, and further, the corresponding parameters are L=1 and dc[1]=4, and then this Update to 5. The address (adr[1]) is updated to 11 according to adr[1]+Lw=9+(1*2)=11. Update the decompressed value (dc[1]) to 5 according to dc[1]+L=4+1=5, which means that 5 symbols ("cacat") from the second input stream 1532 are decoded. Indicates that the Since 5 is less than 8, decompression of the reordered compressed second stream 1542' does not stop.

Next, since the compressed code 100 from the rearranged compressed first stream 1541' has a reverse pointer to NULL, the character code " d" is output together with the corresponding address information and parameters. That is, the corresponding address information includes adr[0]=14, and the corresponding parameters are L=1 and dc[0]=7, which is then updated to 8. Update the decompressed value (dc[0]) to 8 according to dc[0]+L=7+1=8, which means that all eight symbols (“cbcbcbcd”) from the first input stream 1531 are decoded. Indicates that the Therefore, since dc[0] is equal to 8, the decompression of the reordered compressed first stream 1541' is stopped. Now that the decompression of the reordered compressed first stream 1541' is complete, in order to start decompressing the next reordered compressed first stream 1541', address (adr[ 0]) to 0.

Finally, the compressed code 258 from the reordered compressed second stream 1542' provides the multi-symbol string "tac", and the compressed code 258 has the character code "t". , a reverse pointer to 256 whose character code is "a", a reverse pointer to 99 whose character code is "c", and a reverse pointer to NULL. Therefore, when the character codes "t", "a", and "c" are respectively output and then written to the decompressed stream 1560, their positions are reversed. The corresponding address information includes adr[1]=11, and the corresponding parameters are L=3 and dc[1]=5, which is then updated to 8. Compressed code 258 contains three character codes (“tac”) from three symbols of second input stream 1532, so its length (L) is three. The decompressed value (dc[1]) is updated to 8, indicating that all eight symbols (“cacatcat”) from the second input stream 1532 are decoded. Therefore, since dc[1] is equal to 8, decompression of the reordered compressed second stream 1542' is stopped. Now that the decompression of the reordered compressed second stream 1542' is complete, we need to start decompressing the next reordered compressed second stream 1542' at address (adr[ 1]) is updated to 0.

As discussed above, decompressed stream 1560 is formed from decompressed intermediate stream 1555 by reversing the order of the respective character codes within the multi-symbol string. Reversing the order of character codes to create the decompressed stream 1560 may be done during the iterative decompression process or after the decompressed intermediate stream 1555 is completed. . The final result is as seen in FIG. 15C, where the order of character codes "bc" from the compressed code 256 of the reordered compressed first stream 1541' is At 1560, "c" is received in reverse order, followed by "b". The order of the character codes "ac" from the compressed code 256 of the rearranged compressed second stream 1542' is received in the reverse order of "c" followed by "a" in the decompressed stream 1560. be done. The order of the character code "cbc" from the compressed code 258 of the rearranged compressed first stream 1541' is such that in the decompressed stream 1560, "c" is followed by "b", followed by " c" in reverse order. The order of the character code "tac" from the compressed code 258 of the rearranged compressed second stream 1542' is such that in the decompressed stream 1560, "c" is followed by "a", followed by " t'' in reverse order.

Once complete, the resulting decompressed stream 1560 will be the same as the original serial stream 1520 shown in FIG. 15A. In an alternative embodiment, the compressed symbols originating from the reordered compressed first stream 1541' are transferred to the first temporary output stream (characters of the multi-symbol string) stored in the first temporary buffer. The compressed codes starting from the reordered compressed second stream 1542' are then decompressed into a second temporary Decompress as a buffered second temporary output stream (which may or may not contain the character codes of the multi-symbol string in reverse order). The decompressed stream 1560 can then be formed by alternately inputting symbols from the first temporary output stream and the second temporary output stream.

FIG. 16 is a simplified flow diagram illustrating a method for providing decompressed wideword data during communication of wideword data over a data link, in accordance with an exemplary embodiment. This method allows data to be stored in the capture buffer of the interposer circuit during communication over a data link that conforms to a high-speed hierarchical packet-based protocol, without loss of functionality and without loss of information available for analysis. Reduce the amount of data used. The various steps of FIG. 16 can be performed in the interposer circuit 120 and/or the UI computer 110 (i.e., the interposer circuit 120, the UI computer 110, or both) described above, and the complexities associated with conventional solutions may be avoided. It eliminates significant wiring and signal integrity issues, reduces overall cost, and supports faster upload times, for example by using high-bandwidth interfaces (and less raw data). 13A-13C discussed above illustrate an example of the method shown in FIG. 16.

Referring to FIG. 16, in block S1601, a serial stream to be compressed is divided into multiple input streams corresponding to multiple wide words in the serial stream. Each input stream includes a predetermined number of symbols.

In block S1602, parallel compression is performed on multiple input streams to obtain corresponding compressed streams. Each compressed stream includes a plurality of compressed symbols, and each compressed symbol includes at least one character code and at least one reverse pointer. The compressed stream includes at least one compressed code including a multi-symbol string having a plurality of character codes and at least one NoOp entry corresponding to the multi-symbol string. As described above with reference to FIG. 8, each multi-symbol string indicates a compressed symbol representing two or more original input symbols in the input stream; To efficiently locate the first or next compressed arbitrary original input symbol in a compressed stream included in a sequence. If a multi-symbol string contains compressed codes from more than two input symbols, NoOp entries appear in all but the last position of the input symbol in the compressed stream.

In block S1603, the compressed streams are each reordered in a first arriving symbol reordering process to form a plurality of reordered compressed streams. For each compressed stream that has at least one multi-symbol string, each multi-symbol string is moved to the position of the first symbol of that multi-symbol string and the corresponding NoOp entry(s) is shifted from the position of the first symbol. That is, the position of the multi-symbol string and the NoOp entry(s) such that the position of the multi-symbol string comes before the NoOp entry(s) in the recorded compressed stream. is switched.

In block S1604, an uninterrupted compressed output stream is formed by alternately inputting compressed codes from the rearranged compressed stream except for NoOp entries. For example, if there are two wide words, a seamless compressed output stream is formed by interleaving the compressed codes from the two reordered compressed streams. . For example, if there are four widewords, each can be iteratively cycled through the compressed symbols from the four reordered compressed streams to form a seamless compressed output stream. .

In block S1605, decompression of the compressed output stream is initiated by iteratively receiving compressed symbols in the uninterrupted compressed output stream from the reordered different compressed streams. Each compressed code includes at least one character code and at least one reverse pointer. In a compressed stream including at least one multi-symbol string, each multi-symbol string includes a plurality of character codes and a plurality of reverse pointers.

In block S1606, a decompressed intermediate stream is formed by iteratively decoding the compressed symbols from the various compressed streams, following each compressed symbol's inverse pointer. That is, the compressed code is decoded by tracing at least one inverse pointer of each compressed code until a NULL entry is reached and at least one character code is obtained. If the compressed code includes one reverse pointer pointing to a NULL entry, then the compressed code includes a one-character code. If the compressed code includes multiple reverse pointers, and the last reverse pointer points to a NULL entry, then the compressed code each includes multiple character codes, and the compressed code is a multi-symbol string. including.

In block S1607, decompressed streams are formed from the decompressed intermediate streams by reversing the order of the character codes of each multi-symbol string from each of the compressed streams. The order of the remaining character codes remains unchanged. The decompressed stream is output for further processing and analysis. For example, as previously discussed, the decompressed stream can be output to the UI computer 110, which UI computer applies a protocol analyzer to the decompressed stream to analyze the data according to a high speed data protocol. Apply.

17A and 17B are simplified flowcharts illustrating a method for providing decompressed wideword data during communication of wideword data over a data link, according to an exemplary embodiment. In this method, during the communication of data over a data link that conforms to a high-speed hierarchical packet-based protocol, data is stored in the capture buffer of the interposer circuit without loss of functionality and without loss of information available for analysis. It is possible to reduce the amount of data. The various steps of FIGS. 17A and 17B can be performed in the interposer circuit 120 and/or the UI computer 110 described above, eliminating the complex wiring and signal integrity issues associated with traditional solutions and reducing the overall cost. and support faster upload times, e.g. by using high-bandwidth interfaces (and less raw data). 15A-15C discussed above illustrate an example of the method shown in FIGS. 17A and 17B.

Referring to FIG. 17A, at block 1701, a serial stream of data to be compressed is divided into multiple input streams corresponding to multiple wide words in the serial stream. Each input stream includes a predetermined number of symbols.

In block S1702, parallel compression is performed on multiple input streams to obtain corresponding compressed streams. Each compressed stream includes a plurality of compressed symbols, and each compressed symbol includes at least one character code and at least one reverse pointer. Some of the compressed streams have at least one compressed code including a multi-symbol string having multiple character codes and at least one NoOp entry corresponding to the multi-symbol string. As discussed above with reference to FIG. 8, each multi-symbol string indicates a compressed symbol representing two or more original input symbols in the input stream, and the NoOp entry also represents the corresponding multi-symbol string. To efficiently obtain the position of the first original input symbol in a compressed stream included in a column. If a multi-symbol string contains compressed codes from more than two input symbols, NoOp entries appear in all but the last position of the input symbol in the compressed stream.

In block S1703, each NoOp entry in the corresponding compressed stream is deleted, and any compressed code among the plurality of compressed codes following each deleted NoOp entry is inserted into the position of the deleted NoOp entry. By shifting each compressed stream among the plurality of compressed streams. For example, if you delete one NoOp entry, all compressed codes following the NoOp entry in the compressed stream will be shifted by one in the direction of the deleted NoOp entry, and the corresponding compressed A stream is formed. When two adjacent NoOp entries are deleted, all compressed codes following the NoOp entry in the compressed stream are shifted by two in the direction of the deleted NoOp entry, and the reordered corresponding compressed symbols are A stream is formed, and so on.

In block S1704, an uninterrupted compressed output stream is formed by repeatedly inputting compressed codes from the rearranged multiple compressed streams (if there are no deleted NoOp entries). . For example, if there are two wide words, a seamless compressed output stream is formed by interleaving the compressed codes from the two rearranged compressed streams. For example, if there are four widewords, a continuous compressed output stream is formed by repeatedly cycling through each of the compressed symbols from the four permuted compressed streams. If the reordered compressed streams have different numbers of compressed symbols, the compressed symbols added to the end of the longer reordered compressed stream are the unbroken compressed output stream. provided adjacent to the end of.

In block S1705, decompression of the uninterrupted compressed output stream is performed. Generally, this decompression involves iteratively decoding the compressed codes from the uninterrupted compressed output stream according to each reordered compressed stream to obtain the corresponding character codes. and are executed in parallel by reversing the order of the character codes obtained from the compressed code containing the multi-symbols and constructing a decompressed stream from the obtained character codes. With reference to FIG. 17B, consider in more detail the process of performing decompression. The decompressed stream is output for further processing and analysis. For example, as previously discussed, the decompressed stream can be output to the UI computer 110, which UI computer applies a protocol analyzer to the decompressed stream to analyze the data according to a high speed data protocol. Apply.

FIG. 17B is an example implementation of the decompression process shown in block S1705 of FIG. 17A. Referring to FIG. 17B, blocks S1751-S1756 are executed at the current address (adr) in the decompressed stream for each compressed symbol in the compressed output stream. In block S1751, a rearranged compressed stream that includes the compressed code of the current address is identified in the uninterrupted compressed output stream. For example, if the original serial stream contains two widewords, each compressed symbol in the uninterrupted compressed output stream is obtained from one of the two reordered compressed streams. Ru.

In block S1752, the compressed code is decoded by following at least one reverse pointer until a NULL entry is reached and at least one character code is obtained. If the compressed code includes one reverse pointer pointing to a NULL entry, then the compressed code includes a one-character code. If the compressed code includes multiple reverse pointers and the last reverse pointer points to a NULL entry, the compressed code includes multiple character codes each, so that the compressed code is a multi-symbol Contains strings.

In block S1753, the address of the decompressed code is identified. Address (adr) is the first address that the decompressed character code(s) in the decompressed stream should occupy. For example, if the compressed code includes a one-character code, that one-character code will occupy the specified address. If the compressed code contains two character codes, the two character codes are the specified address and the same reordered compressed stream (i.e., the other reordered compressed and so on.

In block S1754, parameters of the code after compression are determined. The parameters include, for example, the length of the code after compression (L) and the decompression value (dc). The length of the compressed code is determined based on the decoding performed by following the inverse pointer in block S1752. In other words, the length corresponds to the number of character codes of the code after compression. Therefore, the length of a compressed code with one character code is L=1, and the length of a compressed code with two character codes is L=2. The decompression value is determined as the cumulative number of decompressed symbols from the same input stream (and thus the same reordered compressed stream) before the current decompressed symbol. If the compressed symbol is the first one of a particular input stream, the decompression value will be 0 since the symbol has not yet been decompressed. For the next compressed code from the same input stream, the decompressed value is the sum of the decompressed value of the previous compressed code and the length of the previous compressed code. Generally, if the compressed code includes a one-character code, the decoded value is incremented by one. Generally, if the compressed code includes a two-character code, the decoded value is incremented by two, and so on.

Block S1755 determines whether the accumulated decompression value is equal to the number of symbols in the original input stream corresponding to the reordered compressed stream. For example, as discussed above, the original input stream may contain eight symbols. If the decompression value is not equal to the number of symbols (block S1755: No), the process proceeds to block S1756, in which the next decompressed symbol from the same reordered compressed stream is Determine the next address. The next address can be determined based on the current address, length, and number of wide words (w) in the serial stream. That is, as described above, the next address is the product of the length (L) and the number (w) added to the current address (adr). The current address is set to the next address determined in the decompressed stream for the next iteration of the same reordered compressed stream.

The process then returns to block S1751, where a reordered compressed stream is identified that includes the next compressed code in the uninterrupted compressed output stream. As we have discussed, the reordered compressed stream is different from the previous reordered compressed stream, which allows the compressed code to be interleaved to perform the decompression. be done. For example, if the original serial stream contains two widewords, the reordered compressed stream is reordered with the reordered compressed first stream to perform decompression. and the compressed second stream. Then repeat the process.

If the decompression value is equal to the number of symbols (block S1755: Yes), it indicates that all compressed symbols from that reordered compressed stream that correspond to symbols in the input stream have been decompressed. , the process continues to block S1757. In block S1757, it is determined whether there are any remaining reordered compressed streams that have not yet been fully decompressed. If there are no rearranged compressed streams remaining (block S1757: No), the process proceeds to block S1758, which will be described later. If there is at least one reordered compressed stream with compressed codes remaining (block S1757: Yes), the process returns to block S1751 where the uninterrupted compressed output stream , a reordered compressed stream containing the next compressed code is identified. At this point, you may have exhausted the compressed symbols from the other reordered compressed stream(s), so the next compressed symbol will be the same reordered compressed stream. It could be from a later stream. Then repeat the process.

In block S1758, the character code(s) from each compressed code of each reordered compressed stream is added to the address in the decompressed stream that corresponds to the current address of the compressed code. A decompressed stream is formed by inputting . Entering the at least one character code includes reversing the order of each character code within the at least one multi-symbol string from each compressed stream. For each multi-symbol string, the first character code in reverse order is entered at the current address, and the remaining character code(s) are available in the same reordered compressed stream. Input to the next consecutive address(es) in the decompressed stream. The order and addresses of the remaining character codes remain unchanged. The final result is a decompressed stream with character codes in the same order as the original serial stream that was split in block S1701 and compressed in S1702 of FIG. 17A above.

FIG. 18 is a simplified block diagram illustrating an example of a computer system that reduces the amount of data stored during communication of data over a high speed data link, in accordance with a representative embodiment.

Referring to FIG. 18, computer system 1800 includes a processing unit 1810 and a memory 1820 for storing instructions executable by processing unit 1810 to perform the processes described herein, as well as for use by a user. A display 1830 and an interface 1840 are included for enabling. Processing unit 1810 is representative of one or more processing devices and is configured to execute software instructions to perform the functions described in various embodiments herein. Processing unit 1810 may be a general purpose computer, a central processing unit, one or more processors, a microprocessor or microcontroller, a state machine, a programmable logic device, a field programmable gate array (FPGA), an application specific integrated circuit (ASIC), or the like. may be implemented using any combination of hardware, software, firmware, hardwired logic, or combinations thereof. The term "processor" specifically encompasses a program or an electronic component capable of implementing machine-executable instructions. References to "processor" shall be construed to include two or more processors or processing cores, such as multi-core processors and/or parallel processors (i.e., multi-core processors and/or parallel processors). It shall be. Processor may also refer to a collection of processors within a single computer system, or to processors distributed among multiple computer systems, such as cloud-based or other multi-site applications. A program includes software instructions that are executed by one or more processors that may be distributed within the same computing device or across multiple computing devices.

Memory 1820 may include main memory and/or static memory (i.e., main memory and/or static memory), where such memory is interconnected to each other and to processing unit 1810 via one or more buses. can communicate with. Memory 1820 stores instructions used to implement some or all aspects of the methods and processes described herein. Memory 1820 may be implemented with, for example, any number, type, and combination of random-access memory (RAM) and read-only memory (ROM), and may further include software algorithms. , and computer programs, all of which can be executed by processing unit 1810 . The different types of ROM and RAM include disk drives, flash memory, electrically programmable read-only memory (EPROM), and electrically erasable and programmable read-only memory (EPROM). EEPROM (electrically erasable and programmable read only memory), register, hard disk, removable disk, tape, compact disk read only memory (CD-ROM), digital versatile disk (DVD), floppy Any number, type, and combination of computer-readable storage media, such as discs, Blu-ray discs, universal serial bus (USB) drives, or any other form of storage media known in the art. It may include a storage medium. If processing unit 1810 includes an FPGA, for example, memory 1820 may include UltraRAM, as described above, or other RAM with read and write capabilities.

Memory 1820 is a tangible storage medium for storing data and executable software instructions that is non-transitory while the software instructions are stored therein. As used herein, the term "non-trasitory" shall be construed as a characteristic of a condition that lasts for a period of time, rather than an eternal characteristic of the condition. The term "non-transitory" specifically negates properties that are temporary, such as carrier waves or signals, or other forms of properties that exist only temporarily in any given location at any given time. That is what it means. Memory 1820 may store software instructions and/or computer readable code (ie, software instructions and/or computer readable code) that enable performance of various functions. Memory 1820 may be secure and/or encrypted (i.e., secure and/or encrypted) or insecure and/or unencrypted (i.e., insecure and/or encrypted). (or both).

Display 1830 may be, for example, a computer monitor, a television, a liquid crystal display (LCD), an organic light emitting diode (OLED), a flat panel display, a solid state display, or a cathode ray tube (CRT). It may be a monitor, such as a display, or an electronic whiteboard. Display 1830 can also provide a graphic user interface (GUI) for displaying and receiving information from a user.

Interface 1840 is configured to provide information and data output by processing unit 1810 and/or memory 1820 (i.e., processing unit 1810 and/or memory 1820) to the user and/or to provide information and data input from the user. A user interface and/or a network interface (ie, a user interface and/or a network interface) may be included for receiving data. That is, interface 1840 enables a user to enter data and control or operate aspects of the processes described herein, and further enables processing unit 1810 to indicate the effects of the user's controls or operations. Make it. Interface 1840 may include one or more user interfaces, such as, for example, a mouse, keyboard, trackball, joystick, haptic device, microphone, video camera, touch pad, touch screen, voice captured by a microphone or video camera, or gesture recognition; Alternatively, other peripherals or controls that enable user feedback from and interaction with the computer workstation 1805 can be connected. Interface 1840 may also include one or more ports, disk drives, wireless antennas, or other types of receiver circuitry.

The above embodiment performs parallel wideword compression on multiple input streams sent through an interposer circuit to obtain corresponding compressed streams, and stores the compressed streams in a capture buffer. It depends on things. For example, as seen in the examples of FIGS. 9, 13A, and 15A above, upon successful compression of one of the input streams, such as according to the LZW compression algorithm, one or more A NoOp entry appears in the corresponding compressed stream.

However, if the input stream contains data that does not have many repetitive patterns, such as random data, wideword compression in interposer circuit 120 (including, for example, an FPGA and/or ASIC) This can be a problem when reading and writing to output storage. Random data typically contains few repeats of previously occurring bytes, resulting in poor compression. A compressed stream of random data, when stored, requires more bits to represent a given output than the original raw uncompressed bytes (8 bits) of the corresponding input stream. This is because the size of the output needs to be able to accommodate the new compressed multi-symbol output encoded as a number greater than 255. A new multi-symbol string (byte string) as a symbol after compression is initially a decimal number in the range 0 to 511, and 9 bits per original uncompressed byte need to be written to the storage medium. Therefore, if a byte cannot be compressed, it still requires 9 bits of storage, which equates to a 12.5 percent increase in storage size, with no benefit (i.e., (not compressed).

The parallel compression described herein relies on the fact that a typical repeating sequence requires only 9 bits to store multiple original uncompressed bytes. However, for random data or other data that does not have many repeating patterns (collectively referred to as "random data"), these repeating sequences are not sufficient to achieve significant data reduction. Additionally, during the compression process, the compression dictionary continues to grow, meaning that new outputs greater than decimal 511 require more bits to be written to the capture buffer 125. This wastes space when uncompressed values that require only 8 bits to write without compression are written with 9, 10, or more bits.

In FIG. 19, the left side shows a compressed output from non-random data, while the right side shows an example of a compressed output from random data. If the input stream contains non-random data, the output after compression will typically contain a value larger than 8 bits, since this value represents a previously occurring sequence of repeated bytes. Generally, the first 512 values (decimal 0-511) require 9 bits, the next 512 values (decimal 512-1023) require 10 bits, and the next 1024 The value (1024-2047 decimal) requires 11 bits, the next 2048 values (2048-4095 decimal) require 12 bits, and so on. The first 512 values can be stored using 9 bits, the next 512 values can be stored using 10 bits, and then all values can be stored using that number of bits, until the maximum dictionary entries are reached. This property of the compression algorithm is useful in decompression because it indicates reading. For example, if the dictionary has a maximum entry of 4095, then 12 bits are used to store the maximum number of values. The algorithm determines the timing of changing from 9 bits to 10 bits (indicated by the broken line in FIG. 19), from 10 bits to 11 bits, and so on. Another method is to store some metadata with each compressed value, which describes the number of bits used for each value. Each value can be expressed using metadata in addition to the optimum number of bits. However, metadata increases storage requirements. Therefore, this "wasted" metadata is not needed to specify the size of each symbol for writing and reading, since the number of values to read is known in advance. The compression algorithm simply starts writing 9 bits, detects that the value of the next highest dictionary entry reaches 512, starts writing 10 bits, and so on. Otherwise, the algorithm would not know where in the bitstream one compressed value begins and the previous compressed value ends, so the algorithm would not know where in the bitstream one compressed value begins and the previous compressed value ends. Data can no longer be successfully reread from storage.

By comparison, in areas of data storage that require 10 or more bits to write and read, more values are written to less than 256 storage if the input stream contains random data. For example, in the typical output illustrated on the right side of Figure 19, after reading the first 511 values, 10 bits are used to read values 2, 61, 32, 9, 47, and 12. However, these are all less than 512, so there should be no need to read the 10 bits. As a result, a large number of uncompressed bytes of 8 bits in the input stream are written to the "post-compressed" output stream as 10 or more bits, thus using more bits than are needed for the uncompressed value. This is a waste of space, causes poor compression due to random data, and has a further knock-on effect by writing too many uncompressed values with more bits than ideal.

According to various embodiments, it is immediately determined if the data in each input stream cannot be compressed well due to not having a repeating pattern (eg, in the case of random data). To make this determination, the interposer circuit 120 applies a window of n bytes (e.g., n=500) to the input stream being compressed and counts the number of clock cycles of the clock that has no output in the corresponding compressed stream. do. Because the interposer circuit 120 observes a sequence previously observed in the current data of the input stream that is a multi-symbol sequence and further outputs it as one new value representing the multi-symbol sequence in the output compressed stream. If you are building a longer sequence, there is no clock cycle output. As discussed above, it is a NoOp function that is underpowered during the clock cycle when compression is active. At the end of the window, interposer circuit 120 determines the ratio of NoOps in the window to the number of bytes/clocks n in the window (NoOp/n). If the NoOp ratio is less than a predetermined ratio threshold, this means that the data in the input stream is not sufficiently compressed. The predetermined threshold for this ratio can be, for example, within a range of about 0.05 to about 0.20. If this ratio is less than a predetermined ratio threshold, compression of the input stream is completely stopped and transmission of the input stream continues without compression. If this ratio is higher than a predetermined ratio threshold, this means that the compression of the data is good and the compression of the input stream continues.

According to an exemplary embodiment, a method is provided for compressing wideword data in real time. The method includes splitting a serial stream into multiple input streams corresponding to multiple widewords of the serial stream, each input stream including a predetermined number of symbols and a capture buffer. Sending an input stream through an interposer circuit, performing parallel compression on the input stream sent through the interposer circuit to obtain multiple corresponding compressed streams, and storing the compressed streams in a capture buffer. one or more compressed streams of the plurality of compressed streams are generated as a by-product of compression and include a NoOp entry indicating a repetition of a corresponding byte; determining the number of NoOp entries occurring in a predetermined number of bytes of each input stream while performing parallel compression of the input stream; determining a ratio of the number of NoOp entries to the predetermined number of bytes; If this ratio exceeds a ratio threshold, then continue performing parallel compression on the input stream and storing the compressed stream; and if this ratio does not exceed a predetermined ratio threshold, this is a NoOp entry. This indicates that parallel compression is not efficient because the number of , or storing the stream after compression, or both) and continuing to send the input stream to the output through the interposer circuit without performing parallel compression, so that only the original 8 bits are stored when storing the data. including ensuring that the information is used.

According to another exemplary embodiment, a non-transitory computer-readable medium stores instructions for providing parallel compressed and decompressed wideword data. When executed by the at least one processor, the instructions are for the at least one processor to split a serial stream into a plurality of input streams corresponding to a plurality of widewords of the serial stream, the instructions comprising: each input stream contains a predetermined number of symbols; controlling the transmission of the input stream through an interposer circuit that includes a capture buffer; and performing parallel compression on this input stream to create corresponding multiple compressions. obtaining a compressed stream and storing the compressed stream in a capture buffer, the one or more compressed streams of the plurality of compressed streams having NoOp entries indicating repetitions of corresponding bytes; and determining the number of NoOp entries that occur in a given number of bytes of each input stream of the plurality of input streams while performing parallel compression of a given number of bytes, and determining the ratio of the number of NoOp entries to the given number of bytes. and if this ratio exceeds a predetermined ratio threshold, perform parallel compression on multiple input streams and continue storing the compressed streams; and if this ratio exceeds a predetermined ratio threshold, Parallel compression performed on multiple input streams and/or storage of the compressed streams (i.e., parallel compression performed on multiple input streams or post-compression (or both) and continue controlling the transmission of multiple input streams through the interposer circuit without performing parallel compression.

According to another exemplary embodiment, the system provides parallel compressed and decompressed wideword data. The system transmits a serial stream of data in a high-speed layered packet-based protocol from a device under test (DUT) to a host computer via a high-speed data link that conforms to a high-speed layered packet-based protocol. It includes a user interface (UI) computer configured to run analyzer software for analysis, and an interposer circuit that connects to the high speed data link and monitors data transmitted between the DUT and the host computer. The interposer circuit includes a capture buffer accessible from the UI computer for storing data transmitted between the DUT and the host computer and for analysis using analyzer software. The interposer circuit further includes at least one processing unit, the processing unit being operable to split the transmitted serial stream of data into a plurality of input streams corresponding to a plurality of widewords of the serial stream. Here, each input stream contains a predetermined number of symbols, and parallel compression is performed on these multiple input streams to obtain multiple corresponding compressed streams, and the compressed stream one or more compressed streams of the plurality of compressed streams include a NoOp entry indicating a repetition of a corresponding byte, and a predetermined number of bytes of parallel compression. determining, while executing, the number of NoOp entries occurring in a predetermined number of bytes of each input stream of the plurality of input streams; determining a ratio of the number of NoOp entries to the predetermined number of bytes; If the threshold is exceeded, continue to perform parallel compression on multiple input streams and store the compressed streams, and if this ratio does not exceed a predetermined ratio threshold, stopping the parallel compression performed on the data and/or storing the compressed stream, the data continuing to be transmitted between the DUT and the host computer without parallel compression; be programmed to do so.

FIG. 20 illustrates an example of wideword data symbols configured for parallel data compression with high compression efficiency, according to a representative embodiment.

Referring to FIG. 20, the wide word 2020 is divided into 256 input streams arranged as parallel input streams to perform parallel compression, as previously discussed with reference to FIGS. 6, 13A, and 15A, for example. Contains the input stream. In the example shown, the original serial stream is "0FAC1500...B00FAC1500...B00FAC1500...B001020407...0517192230..." and the bytes of the original serial stream are divided into 256 input streams. There is. Assume that the first three bytes of each input stream contain compressible data such as non-random configuration data and headers. It is further assumed that bytes after the third byte in each input stream contain incompressible data, such as, for example, random payload data in a transaction layer packet (TLP). The compression algorithm may be, for example, the LZW compression algorithm or other compression algorithm derived from, for example, the LZ78 compression algorithm.

The point at which the input data becomes incompressible is not known in advance. Therefore, in order to identify where the data becomes uncompressible, we perform compression and then analyze its performance in real time to determine when the input data for each input stream stops being compressed as a practical matter. to decide. More specifically, successful compression of an input stream generates NoOp entries representing repeated bytes of the corresponding compressed output stream, e.g. using a modified version of LZW, as discussed below. , the success of compression can be determined by counting the number of NoOp entries for a given number of bytes of the output stream after compression.

FIG. 20 illustrates a process for determining compression success for an exemplary first input stream only. The first three bytes of the first input stream have the same hexadecimal value 0F (ie, decimal 15). Since this byte appears for the first time in the first input stream, the first occurrence of the hexadecimal value 0F is converted to the decimal number 15 in the first clock cycle of the first (post-compressed) output stream. On the next clock cycle, the algorithm looks for another previously seen hexadecimal value 0F and tries to build the longest possible subsequence, thus inputting a NoOp entry into the first output stream. On the next clock cycle, the algorithm looks for another hex value 0F and outputs the next output value 256 representing the original 2 bytes 0F0F in the first output stream. As a result, the first output stream compression unit 2022 produces a character string of 15, NoOp, and 256. However, the next two bytes 1 and 17, which are read in the next two clock cycles, are seen for the first time, so the output value is only the uncompressed equivalent of the original input value. This generates character strings of decimal 1 (ie, from hexadecimal 1) and decimal 23 (ie, from hexadecimal 17) in the uncompressed portion 2024 of the first output stream.

In this simplified example, there is one NoOp in three output entries, so the NoOp ratio of the first three output values of the first output stream is as high as 0.33. If "random data" of the payload appears and no NoOp entry is generated, the NoOp ratio of the next two output values will be as low as 0. Note that this example is for illustrative purposes only. In fact, if there are only two values to determine that the data is random and incompressible, it is too few to be accurate or useful. Thus, according to various embodiments, an n-byte window (eg, a discrete window) is applied to determine the NoOp ratio, where n is a predetermined value. In our experience, n=500 has provided good results in determining whether the input data compresses well, but other values of n may be incorporated without departing from the scope of the present teachings.

To determine whether the data in the input stream is random and therefore cannot be compressed successfully, the ratio between the number of NoOp entries and the number of bytes per window n is compared to a predetermined ratio threshold. The predetermined ratio threshold for this ratio can be, for example, within a range of about 0.05 to about 0.20. More specifically, the predetermined ratio threshold for this ratio may be, for example, about 0.10 to provide a good indication if the data is random. It should be understood that other predetermined ratio thresholds may be applied without departing from the scope of the present teachings.

The window size should be small enough with respect to the data that you can quickly identify when the input stream becomes incompressible, but not so small that applying the window makes the results unreliable. do not have. For example, in the illustrated example of Figure 20, a discrete window of n = 3 bytes immediately indicates when the data becomes incompressible, but does not accurately reflect the nature of the data as to whether it is random or not. . If the discrete window is too large, there will be a delay in determining when the data becomes uncompressible. For example, if n=5, the NoOp ratio is 1/5=0.2, which means that the compressibility test is passed even though the flow of random data has already started.

In one embodiment, the window may be a discrete window of n bytes. At the end of the discrete window, the discrete window is shifted to cover the next set of n bytes. In an alternative embodiment, the window may be a sliding window of n bytes, sliding by one byte each time the end of the sliding window is reached. In this case, a temporary buffer is used to form a sliding window that holds n bytes of the capture buffer, where the n bytes of compressed content are the sliding window. The number of NoOps is counted across the contents of the current window. The temporary buffer may be, for example, a first-in-first-out (FIFO) buffer that stores the current compressed value (push to the beginning) and deletes the n+1th compressed value backwards (pops from the end). In another embodiment, this ratio is only checked every n bytes without using a window.

FIG. 21 is a flowchart of a method for improving compression of wide word data in real time, according to an exemplary embodiment. In this method, during the communication of data over a data link that conforms to a high-speed hierarchical packet-based protocol, data is stored in the capture buffer of the interposer circuit without loss of functionality and without loss of information available for analysis. It is possible to reduce the amount of data. Furthermore, the method can stop compression in real time and continue forwarding the input stream without compression whenever the compression process becomes inefficient with respect to storage. The various steps of FIG. 21 can be performed by interposer circuit 120 and/or UI computer 110, as described above.

Referring to FIG. 21, in block S2111, the serial stream of data to be compressed is divided into multiple input streams corresponding to multiple wide words in the serial stream. Each input stream includes a predetermined number of symbols. As previously discussed, each input stream may also include compressible (non-random) data and non-compressible (random) data.

At block S2112, the input stream is sent through an interposer circuit that includes a capture buffer. An input stream is sent, for example, from DUT 140 to UI computer 110 and/or host computer 150 (ie, UI computer 110 and/or host computer 150).

In block S2113, parallel compression is performed on the input stream transmitted through the interposer circuit to obtain a corresponding compressed stream, and this compressed stream is stored in the capture buffer. After this parallel compression, one or more compressed output streams corresponding to the input stream generate NoOp entries indicating repetitions of the bytes of the respective input stream. Compression is controlled by a clock having a predetermined clock period, and a compression determination is performed for each input symbol of the input stream every clock period. Note that if the current byte is a repetition of a previous consecutive byte in the input stream, there is no output in the corresponding clock cycle, i.e., there is no operation (NoOp entry) in that clock cycle. ) is shown.

In block S2114, the number of NoOp entries occurring in a predetermined number of bytes (n) of each input stream of the plurality of input streams is determined while performing parallel compression of a predetermined number of bytes. By counting the number of clock cycles in which compression output is skipped (ie, NoOp) while performing parallel compression, the number of NoOp entries that occur in a predetermined number of bytes can be determined. The number of clock cycles to skip compressed output will be equal to the number of NoOp entries. In one embodiment, the number of clock cycles to skip compressed output can be counted using a counter.

In one embodiment, the number of NoOp entries is determined by applying a window to the input stream, where the size of the window is equal to a predetermined number of bytes (n). That is, apply an n-byte window, determine the number of NoOp entries in the window, and then move the n-byte window to the next set of n-bytes.

In block S2115, the ratio of the number of NoOp entries to the predetermined number of bytes is determined for each input stream. That is, ratio=NoOp entries/n, where n is the number of bytes within the window that determines the ratio. It is worth noting that, as mentioned above, NoOp entries are generated temporarily to indicate iterations due to the nature of the compression algorithm and are not stored in the capture buffer. Thus, although NoOp entries appear in effect as a by-product of the compression algorithm, they are used to identify the presence of random data, according to a representative embodiment.

Block S2116 determines whether the ratio exceeds a predetermined ratio threshold. In one embodiment, this determination is made for each input stream. In an alternative embodiment, the determination as to whether this ratio exceeds a predetermined ratio threshold is made, for example, by using one of the input streams as a primary compressor and notifying the compressor of the other input stream. , is done for all parallel input streams. As previously discussed, for example, the predetermined ratio threshold may range from about 0.05 to about 0.20. If this ratio exceeds the predetermined ratio threshold (block S2116: Yes), this indicates compressible (non-random) data in the input stream, so , the parallel compression and storage of the compressed data continues. This is indicated by resetting the count to zero in block S2117 and restarting the count as in block S2113, which continues parallel compression with the next predetermined number (n) of bytes of the input stream.

If this ratio does not exceed the predetermined ratio threshold (block S2116: No), indicating incompressible (random) data, parallel compression and storage of the input stream is stopped. Thereafter, sending the input stream through the interposer circuit may continue at block S2118 without performing parallel compression. That is, data transmission continues with the clear code rather than the compressed code. As discussed above, if this ratio does not exceed a predetermined ratio threshold, this indicates that the number of NoOp entries is too small for parallel compression to be efficient. Once the ratio for each input stream is determined, compression of the input streams can be stopped individually. Once an input stream is used as a primary compressor to determine the ratio of all input streams, the primary compressor flags data that is no longer compressible with respect to other input streams. In one embodiment, this ratio is subsequently determined for this input stream, and compression or storage can be resumed once the ratio is again favorable.

The embodiment described above has many advantages. First, it is easy to implement. Only a counter is needed to count the number of times a clock cycle skips an output (ie, NoOp). The counter is checked every fixed number of clock cycles (eg, in a discrete window) to determine whether the data is random. The NoOp ratio measured over time is a proxy measure for compression ratio. Furthermore, if the data is not random, the normal LZW algorithm continues unchanged and continues to operate in real time.

Second, this embodiment limits the upper bound on the number of bytes that fail compression to n x wide words. Here, n is the number of bytes in the window, for example n=500. For example, if the wideword is 256, the uncompressed bytes written to the capture buffer are at most 128 Kb, which typically corresponds to less than 1% of the total data in the input data stream. When random data is encountered, stop compression as soon as possible before the output file of the corresponding compressed data stream becomes larger than the corresponding input file, so that the output of the compression process does not become larger than the input to the compression process. Do it like this.

Third, the input data stream can start with non-random data, allowing successful compression before transitioning to random data. This occurs, for example, if the link is first in power-up mode before moving on to data transfer, in which case some random data of its payload is sent. This window allows this random data payload to be used even in such situations, even if it appears later in the data stream and eventually becomes the dominant traffic type on the operational link. ensure that it is recognized.

All of the foregoing embodiments improve the functionality of a computer and inherently improve the functionality of computers and/or other processing devices, such as UI computer 110 and interposer circuit 120 (i.e., computers such as UI computer 110 and interposer circuit 120, or other processing devices). (processing devices, and/or both); In particular, the parallel compression and decompression techniques described herein provide data very quickly with high bandwidth from the interposer circuit 120 to the UI computer 110, and/or the UI computer 110 hosts allows real-time processing and analysis of all data by a protocol analyzer (UI computer 110, a protocol analyzer hosted by UI computer 110, or both). Additionally, the parallel compression and decompression techniques described herein track the location of data primarily based on the reordering of compression symbols in the stream after compression, so they require very little memory to run. Become. Furthermore, this parallel compression and decompression technique allows compression and decompression to be performed while viewing the code in real time, ie, without backtracking. Compression can also be monitored and interrupted if the nature of the data being compressed does not yield useful results.

Although the invention has been illustrated and described in detail in the drawings and foregoing description, such illustrations and description are to be regarded as illustrative or exemplary and not as limiting, and the invention is It is not limited to the disclosed embodiments. Those skilled in the art will understand and be able to make other variations to the disclosed embodiments from consideration of the drawings, disclosure, and appended claims in practicing the claimed invention. can. In the claims, the word "comprising" does not exclude other elements or steps, and the indefinite article "a" or "an" does not exclude a plurality. The mere fact that certain measures are recited in mutually different dependent claims does not indicate that a combination of these measures cannot be used to advantage.

Aspects of the invention may be embodied as an apparatus, method, or computer program product. Accordingly, aspects of the invention may take the form of an entirely software embodiment (including firmware, resident software, microcode, etc.) or an embodiment combining software and hardware aspects. All of these may be collectively referred to herein as "circuits," "modules," or "systems." Additionally, aspects of the invention may take the form of a computer program product embodied in one or more computer-readable media having computer-executable code embodied thereon.

Although exemplary embodiments are disclosed herein, one of ordinary skill in the art recognizes that many variations are possible in accordance with the present teachings and are within the scope of the following claims. . Accordingly, the invention is not to be restricted except as within the scope of the appended claims.

The Abstract of this Disclosure is provided in compliance with 37 CFR 1.72(b) and is submitted with the understanding that it will not be used to interpret or limit the scope or meaning of the claims. . Furthermore, in the preceding Detailed Description, various features may be grouped together or described in a single embodiment in order to simplify the disclosure. This disclosure is not to be interpreted as reflecting an intention that the claimed embodiments require more features than are expressly recited in each claim. Rather, as the appended claims reflect, inventive subject matter may be directed to less than all features of any one of the disclosed embodiments. Thus, the following claims are hereby incorporated into the Detailed Description, with each claim standing on its own as defining separately claimed subject matter.

Claims (10)

During the communication of data between the system under test and the protocol analyzer for analysis via a data link that conforms to a high-speed layered packet-based protocol, without loss of functionality and the loss of information available for said analysis. A method for reducing the amount of data stored in a capture buffer of an interposer circuit, comprising:
Perform a data integrity check of the data in real time, and if the data integrity check indicates that the data is correct, then omitting data integrity bits corresponding to the data integrity check from being stored in the capture buffer;
performing ACK/NACK matching in real time to indicate successful or failed arrival of the TLP of the data using acknowledgment and negative acknowledgment (ACK/NACK) packets; omitting from storing in the capture buffer;
deleting and/or reducing fields from the TLP and/or the DLLP of the data to be stored in the capture buffer in real time. further comprising compressing the payload of the TLP and/or the DLLP of the data to be stored in the capture buffer in parallel;
Compressing the TLP and/or DLLP payload of the data includes receiving symbols from the TLP and/or DLLP payload in a plurality of serial lanes at the interposer circuit, and compressing the TLP and/or DLLP payload of the data. deskewing the symbols from the payload of the DLLP into widewords arriving at each clock of a clock cycle; and arranging the widewords into input streams, each input stream arriving at each clock of the clock cycle. including symbols from the same position of each wideword arriving at a clock; compressing the arranged deskewed symbols using a hash table; and storing the compressed symbols in the capture buffer. including
The method according to claim 1. Performing the data integrity check of the data in real time includes checking a cyclic redundancy check (CRC) in the TLP and the DLLP on the interposer circuit, and checking a frame parity bit in the TLP on the interposer circuit. including doing;
Omitting from storing the data integrity bits is removing a checksum of the CRC indicating no errors, and storing a checksum of the CRC indicating errors in the capture buffer. , omitting a frame parity bit indicating no error, and storing the frame parity bit indicating an error in the capture buffer;
The method according to claim 1. The ACK/NACK packet is a DLLP,
2. Instead of storing the ACK/NACK DLLP, each of the TLPs includes metadata appended within the capture buffer, the metadata indicating the ACK/NACK status of the respective TLP. The method described in. Deleting the field from the TLP and/or the DLLP is deleting a known field with a fixed value and/or a null value, the known field being restored at a user interface; deleting a framing token indicating a start and end point of a packet flow of the TLP and/or the DLLP, wherein the framing token is replaced with a smaller symbol or the framing token is deleted; 2. The method of claim 1, comprising one or more of: removing fields identified as non-essential based on settings entered into the user interface. configured to run analyzer software that analyzes data in the high-speed layered packet-based protocol from the device under test (DUT) to the host computer via a high-speed data link compliant with the high-speed layered packet-based protocol; a user interface (UI) computer;
an interposer circuit connected to the high speed data link to monitor the data transmitted between the DUT and the host computer, the interposer circuit configured to monitor the data transmitted between the DUT and the host computer; a capture buffer for storing the data to be accessed by the UI computer for analysis with the analyzer software, the interposer circuit comprising:
Performing a data integrity check of the data in real time, and if the data integrity check indicates that the data is correct, processing a transaction layer packet (TLP) and a data link layer packet (DLLP) of the data. omitting data integrity bits corresponding to the data integrity check from storing in the capture buffer;
performing ACK/NACK matching in real time to indicate successful or failed arrival of the TLP of the data using acknowledgment and negative acknowledgment (ACK/NACK) packets; omitting from storing in the capture buffer;
removing and/or reducing fields in real time from the TLP and/or the DLLP of the data to be stored in the capture buffer. The interposer circuit includes:
performing the data integrity check of the data in real time by checking a cyclic redundancy check (CRC) in the TLP on the interposer circuit and the DLLP and checking a frame parity bit in the TLP on the interposer circuit; to do and
Deleting a checksum of the CRC indicating that there is no error, storing the checksum of the CRC indicating an error in the capture buffer, and omitting a frame parity bit indicating that there is no error. and storing frame parity bits indicative of an error in the capture buffer, thereby omitting the data integrity bits from storage. The system described. The ACK/NACK packet is a DLLP,
Instead of storing the ACK/NACK DLLP, each of the TLPs includes metadata appended within the capture buffer, the metadata indicating the ACK/NACK status of the respective TLP;
The system according to claim 6. The interposer circuit includes:
deleting a known field with a fixed value and/or an empty value, the known field being restored in a user interface;
deleting a framing token indicating a start and end point of a packet flow of the TLP and/or the DLLP, wherein the framing token is replaced with a smaller symbol or the framing token is deleted;
removing said fields from said TLP and/or said DLLP by performing one or more of the following: removing fields identified as non-essential based on settings entered into said user interface; 7. The system of claim 6, wherein the system is programmed to: 7. The system of claim 6, wherein the interposer circuit is programmed to reduce the fields from the TLP by reducing the size of various address fields of the TLP.