dataesr/scientific-paragraphs-categorization huggingface dataset:
A bitmap representation of the dataset is used, which does not scale well to large datasets that have long tail distributions (i. e. many items but short transactions). They used only very small datasets in experiments (max. 19 MB) despite using a high-end workstation (two Tesla C2050 GPUs), and absolute execution times are difficult to infer from their figures. Finally, an implementation based on Micron's Automata processor is proposed in  [Wang et al. 2015]. They obtain noticeable acceleration compared to Borgelt's Apriori sortware tool and a multi-thread implementation of the Eclat algorithm. Their approach appears competitive with GPUaccelerated Eclat running on GPU NVidia Kepler K20C  [Zhang et al. 2013a ].
Eclat Zhang et al. proposed to accelerate Eclat using GPU  [Zhang et al. 2013a]. Candidates enumeration takes place on the CPU, while support counting operations take place on the GPU. A vertical representation of the dataset is stored in the memory of the GPU as bitsets. The intersection of transactions lists is thus a AND operation taking place on the GPU, and the support is computed by counting the number of 1 bits in the resulting bitset. The authors evaluate their solution on a Nvidia Tesla S1070 GPU, and report a 6 to 30 speedup compared to software FIM implementations. A similar acceleration was also performed on FPGA  [Zhang et al. 2013b ]. The main difference with GPU acceleration stems from the lack of memory on the FPGA. Thus, bitsets are stored in main memory and the FPGA only has a small cache.
FP-growth Hardware acceleration of FP-Growth with systolic trees has been proposed in  [Sun et al. 2008]. They noted that the size of the systolic tree grows more than exponentially with the number of frequent items the tree can handle, which limits hardware accelerators to only a few frequent items, typically four. To overcome this limitation they proposed to generate sub-databases by performing projection of the original database on a few items. These sub-databases have to be processed iteratively with the systolic tree and the results have to be merged together. Experiments with known datasets were performed in  [Sun and Zambreno 2011]  with a systolic tree limited to four frequent items. The mining times are compared to a software implementation of FP-Growth. The hardware accelerator speeds mining up when the number of frequent items is low, but there may be no acceleration at all when database projection operations are needed.
Support counting unit The internal implementation of a single support counting unit is given Figure  3. A lot of care has been taken optimizing every bit of this unit in order to have as many of them as possible fit into the FPGA. Some elements are now relatively common in the field of FPGA-accelerated FIM  [Baker and Prasanna 2005; Baker and Prasanna 2006; Wen et al. 2008 ]: a small RAM stores the pattern, an item comparator checks for inclusion in the received dataset transactions, and a counter keeps track of the pattern support. However, the unit we propose differs on several fundamental points: -the absence of address comparator, -the simplified item comparator, -the ability to handle transaction weights, -the absence of per-unit controller. As proposed in  [Wang et al. 2015 ] for FIM acceleration with Micron's Automata Processor, we use a special item value as delimiter of the end of patterns and transactions.
To our knowledge, no related work has been proposed to handle transaction weights. Many software implementations perform de-duplication of identical transactions after filtering infrequent items. This operation enables to reduce the dataset size, sometimes by one order of magnitude depending on the characteristics of the data. This is particularly beneficial for hardware acceleration where the dataset is commonly sent one item at a time to the units. In the proposed implementation, the transaction weight is handled and is sent to units at the clock cycle that follows the end of the transaction. The units add the weight to the support counter instead of adding 1. In fact, the proposed unit features no actual controller. Most control signals are global and are generated by the main support counting controller, as illustrated in Figure  2.
That way the controlling application can store only the parts of the stream that do contain monitored patterns, for later more thorough analysis. To that end, the mining controller has to know as early as possible when any of the monitored patterns is found in the mined dataset/stream transactions. This event can also serve as wake-up signal for any controlling software, so for power-saving purposes the CPU (if any) can be kept in its lowest-power sleep mode most of the time. For FIM acceleration, this signal can also be used to reduce the dataset size between iterations of the Apriori algorithm by removing unuseful items and transactions. So each unit can output two event signals (if enabled at synthesis time). These signals are gathered and routed back to the mining controller using a hardware tree similar to the data distribution tree described in section 4.
In both cases, strictly all LUT primitives of the template are used, which makes these two templates optimal. Approximately half of the slice registers are either used or unusable because of restrictions due to LUTRAM usage in the same slice. The remaining registers are needed for the global distribution tree, with a welcomed little margin because this tree is placed and routed with the automated Vivado design suite. Our placement scripts are not fully automatic. We created one basic placement routine that fills a specified rectangle area by placing units using a zig-zag path. To completely fill our FPGA, this routine is called around 10 to 15 times, with manually-specified coordinates, for each supported template height value. We felt this was an acceptable enough solution to efficiently handle the FPGA black boxes and other local non-uniformities of the reconfigurable fabric.
With high-speed data transfer through PCI-Express or from on-board DDR memory, the entire FPGA can be reconfigured in as low as 72 ms. Also once programmed, the FPGA can be used for any number of different datasets, so the FPGA programming time is generally not an issue. There is however an area of the FPGA without LUTRAM primitives. It represents approximately 6% of the total reconfigurable FPGA area. LUTRAMs are needed for the itemset RAM of each unit, so no unit can be placed in that area. Even with this limitation, and with some area margin taken to ease placement and routing of the large design section PCIe+RIFFA+Controller, the global LUT usage is around 90%. This is exceptionally high compared to the usual objective of 80% for large FPGA designs. With a global working frequency of at least 250 MHz, the proposed design architecture enables to very efficiently use the FPGA resources.
Data throughput As one item is processed per clock cycle, with our 250 MHz implementation the maximum throughput ranges from 250 MB/s for 8-bit item encoding to 1 GB/s for 32-bit item encoding, regardless of the fact that it is a dataset being processed offline or a data stream being monitored online. We highlight the fact that during Apriori FIM, our hardware accelerator behaves strictly the same way as it would for online sequence matching on an uninterruptible data stream.
APPLICATION: APRIORI ACCELERATION We demonstrate the efficiency of our architecture using the batch Apriori FIM application, because the underlying generate-and-test approach can be used for a variety of mining tasks, including sequence mining, whether from offline batch or online stream. There are also many implementations to compare to, in hardware as well as in software, which is not the case for stream sequence mining. Note that the dataset filtering and sorting steps and the need for dataset re-scanning are specific to batch-based applications. However, the acceleration of the core support counting functionality of the Apriori FIM application is representative of stream mining (user-specified sequences or itemsets).
Dataset loading and filtering In the usual software FIM world, the dataset loading steps are the following: (1) read the dataset file from disk, (2) remove infrequent items, (3) sort transactions so items are always in the same order, (4) de-duplicate identical transactions. Some of these operations may be performed in a different order, particularly with trie-based storage of transactions. The usual FPGA-accelerated Apriori world presents two differences: -items are re-coded using the range 0 to #items -1, -identical transactions are not de-duplicated. Re-coding items enables to use hardware units tailored to just the minimum number of useful bits, and to reduce the size of data transfers between the computer and the accelerator. The reason for not de-duplicating identical transactions is generally due to hardware constraints: handling a per-transaction weight requires more complex data transfer protocols, hence an increased design complexity, and usually larger support counting units, which reduces the number of units that can fit in the FPGA.
HW / SW parallelism When the number of candidate (K + 1)-itemsets is higher than the number of support counting units, the candidates are grouped into several batches that are iteratively sent to the FPGA. The order of candidates is not relevant, so they are simply grouped by following the order in which the generation algorithm produces them. Each batch is created and processed in several steps: (1) build a batch of candidates, (2) send the batch of candidates to the FPGA, (3) send the dataset to the FPGA, (4) get the support values from the FPGA, (5) drop infrequent itemsets. The processing of batches is highly pipelined in order to perform as many software tasks as possible during data transfers. From the software side, data transfers are actually handled by the RIFFA driver and performed by the autonomous DMA of the processor.
This uses nearly no CPU time so it is done in parallel with the other software tasks. Figure  8  illustrates how these steps are orchestrated between the software and hardware sides, and shows how the processing pipeline is initialized. Tasks are represented by boxes and data transfers are highlighted with large grey arrows. Building batches of candidates (K + 1)-itemsets is performed using a well-known technique, briefly described here. The frequent K-itemsets obtained at the previous iteration of the Apriori algorithm are scanned. From two K-itemsets of the form P ∪ {a} and P ∪ {b}, where P is a frequent (K -1)-itemsets, the candidate P ∪ {a, b} is built. This candidate is also filtered by checking that all other K-itemsets it contains are also frequent. This is done with a software hash table that contains hashes of all frequent K-itemsets, which is both very fast and scalable.
The support counting process begins by building the first batch of candidates of size K + 1. Then this first batch is sent to the FPGA, followed by the dataset for support counting. While the dataset is being sent, the computer builds the second batch of candidates. The support counters of the first batch are sent back to the computer, which is simultaneously sending the second batch to the FPGA. When both operations are finished, the dataset is sent again to the FPGA for support counting of the second batch. In the meantime, the computer drops infrequent itemsets from the first batch, then it builds the third batch while the dataset is still being sent. The processing pipeline is now initialized and batches are processed with maximum computeraccelerator parallelism. This process continues until all candidates have been either filtered out or processed in the batches.
Splitting large datasets Similarly to the fact that there can be more candidates than there are hardware counting units, which forces to process candidates into several batches, the range of the hardware counters can be shorter than what would be needed to hold the worst-case itemset frequency. To that end, after loading and filtering the dataset, the frequencies of all items are considered. Indeed, no itemset can be more frequent than any of its items. In case the hardware counters are too short to hold this worst-case itemset frequency, the dataset is split into several partial datasets such that for each one, the worst-case itemset frequency is guaranteed to fit in the hardware counters. At support counting time, the dataset is not sent to the FPGA in one go as previously illustrated Figure  8.
Instead, the partial datasets are sent one at a time. Hardware counters are also read and cleared between partial datasets. However, there might be transactions whose weight value can't fit in the hardware counters, even taken alone. In this situation, these transactions are isolated and each forms a partial dataset. Such special partial dataset is sent to the FPGA with transaction weight forced to 1, and when later receiving support values, the values are multiplied by the original transaction weight. This technique enables to use hardware units with short counters even for very large datasets. This enables to instantiate in the FPGA a higher number of units compared to using counters large enough, potentially speeding up the support counting operation.
Datasets Datasets chosen from related works are used in order to compare the performance of our solution against other recent implementations. Details are given in Table  II. T10I4D100K and T40I10D100K are standard synthetic datasets from  [FIMI Repository 2003] , used in  [Baker and Prasanna 2005; Baker and Prasanna 2006; Thoni and Strey 2009]. This enables to compare against competing FPGA implementations of the Apriori algorithm. Pumsb, accidents and webdocs are standard real-world datasets from [FIMI Repository 2003], webdocs5x is a synthetic dataset obtained by replicating webdocs 5 times. They are used in  [Wang et al. 2015] , enabling to compare against an implementation of the Apriori algorithm using Micron Automata Processor. T40I10D03N500K, T40I10D03N1000K, T60I20D05N500K and T90I20D05N500K are used in  [Zhang et al.
2013b ]. This enables to compare against an FPGA-accelerated implementation of the Eclat algorithm. The datasets are generated with the tool IBM Market-Basket Synthetic Data Generator  [IBM 2012 ]. The five other datasets, chess, BMS-WebView-2, connect, BMS-POS and kosarak are used in  [Sun and Zambreno 2011]. This enables to compare against an FPGA-accelerated implementation of the FP-Growth algorithm.
In order to reduce the dependency of results upon disk I/O speed, each dataset is pre-loaded into main RAM before any FIM operation, accelerated or not. We highlight that the available PCIe data throughput largely exceeds our needs: our FPGA IP processes one item per clock cycle, so for 16-bit items only 500 MB/s are required, whereas the PCIe 2. 0 8x interface provides up to 4 GB/s.
Comparison with FPGA-accelerated FP-Growth We compare with  [Sun and Zambreno 2011]  as they provide results with several datasets and broad ranges of support values. They implemented a systolic tree of depth 4, which means 4 frequent items. Handling more frequent items is done by performing dataset projections. The transactions must be sorted before sending them to the systolic tree, this is a light limitation we also have. Table  III  shows execution times for their approach and ours for a few support values. It is important to highlight that the datasets are small and dense, and the support values that are used lead to millions, sometimes billions of frequent itemsets. Obviously in this kind of situation only the number of itemsets can be counted. There is even a peak at 1. 4 × 10 17 for BMS-WebView-2 with minimum support 2.
However during generation, the Apriori algorithm stores all K-itemsets simultaneously in main RAM memory. So for extreme amounts of itemsets, RAM requirements are often excessive and our approach fails (noted swap in the table). Anyhow, as the number of itemsets increases, it becomes Depending on the dataset, our approach achieves better or similar performance than the systolic tree. Interestingly, our speedup is the highest when the number of frequent itemsets is reasonable (datasets BMS-POS and kosarak). The bottleneck of their approach is probably the dataset projections they need to perform, which are CPU tasks. When there are relatively few itemsets to find, the cost of these projections is not amortized. So it makes sense to also compare against one of the fastest software tools, LCM 3.
0 (see our comparison of SW tools in section 6. 7). Unsurprisingly for these small and dense datasets, the depth-first, memory-efficient LCM 3. 0 approach is much faster than the systolic tree (and faster than our approach too). Hardware acceleration is probably now only pertinent for much larger, lower-density datasets. Fortunately, these so called long-tailed dataset are very frequent, in particular in Web data and retail data  [Anderson 2006 ].
Comparison with FPGA-accelerated Eclat Table  IV  shows execution times of our VC709 platform, compared to an FPGA-accelerated implementation of the Eclat algorithm  [Zhang et al. 2013b ]. The configuration with 9360 units is used for all datasets except T40I10D03N1000K where the 11636-units configuration is used due to the low number of frequent items. For these datasets and support values, their platform seems to perform much better than ours with speedups ranging from 2. 87x to 7. 22x. However, the underlying hardware is different. Our Xilinx Virtex-7 xc7vx609t FPGA is composed of 108k logic slices, they use four Altera Statix III EP3SE260 FPGAs, each having 102k Adaptive Logic Modules (ALM). For our support counting implementation, each Xilinx slice is roughly equivalent to 2 Altera ALMs.
So with the amount of hardware resources available on their platform, our acceleration technique would run twice faster. They also use large on-board RAM with lowlatency access. This makes their platform more complex and probably more power-consuming. The very limited test set makes it difficult to further compare both platforms. It would also be interesting to know how fast the on-board RAM limit is reached and mining fails, like in  [Wang et al. 2015 ] with dataset T100D20M. Our accelerator is not limited by on-board RAM.
Comparison with Micron Automata In Figures 9 and 10 the support counting times with Micron Automata Processor board (noted AP) and of our FPGA-accelerated platform (noted VC709) are shown. We use counting time instead of A:16 overall execution time because only counting time could be precisely extracted from the reference paper  [Wang et al. 2015 ]. The configuration with 11636 units is used for pumsb and accidents, and 7788 units are used for webdocs and webdocs5x It can be observed that our platform is much faster than AP for all datasets and for all support values, with a maximum speedup of 12. 3x for dataset pumsb (support 52%). This performance gap has several explanations: -number of counting units and clock frequency, -symbol replacement time, -de-duplication of dataset transactions.
The AP board is clocked at 133 MHz and is configured with 18432 counting units. Our VC709 board is clocked at 250 MHz, so with the 11636-units configuration it is theoretically faster than the AP board by 18. 7%. Also, when using 9-bit to 16-bit item encoding, the item rate is halved on the AP board. On our VC709 board the item rate is unchanged, so we provide a theoretical speedup of 90. 9% with 9-bit to 12-bit encodings (9360 units) and 58. 8% with 13-bit to 16-bit encodings (7788 units). Our FPGA also supports virtually any item width, whereas it is unknown if more that 16-bit items can be used one the AP board. The symbol replacement time, in the worst case, is 45 ms for the AP board, but only 1. 49 ms for the VC709 board with the 11636-units configuration. However this parameter should only be relevant for very small filtered datasets, e.
g. pumsb. The AP board can only increment support counters by 1 when counting. This is the main drawback of their implementation and perhaps of the hardware itself. Our FPGA counting unit is specifically designed to enable adding transaction weights to support counters. So during dataset loading, we perform de-duplication of filtered transactions. The size of the dataset pumsb is then reduced by the factor 4. 88x for support 52%. This de-duplication feature has a direct consequence on the time needed to send the dataset to the accelerator. Similarly for the dataset webdocs5x (created by concatenating webdocs 5 times), there is a minimum guaranteed speedup of 5x thanks to de-duplication. The advantages of the VC709 board over the AP board are not limited to counting speed. The AP board is composed of 48 Automata Processor chips, where each has a 150 mm² die size on 50 nm technology node and a 4 W power consumption  [Micron Technology, Inc.
Comparison with previous FPGA-accelerated Apriori We compare against  [Thoni and Strey 2009]  because their target FPGA technology (Xilinx Virtex-5) is very close to ours (Xilinx Virtex-7). They also noted that the previous results in  [Baker and Prasanna 2006]  were wrong. Moreover, the results from  [Baker and Prasanna 2005]  can also be verified to be wrong due to erroneous estimation of the numbers of candidates. So the works from  [Thoni and Strey 2009]  are the most pertinent. Two datasets from  [FIMI Repository 2003]  are used: T10I4D100K and T40I10D100K. We use the configuration with 9360 counting units, all working at 250 MHz. They use 1116 counting units working at 170 MHz. Like ours, their architecture is able to process one item per clock cycle. This brings a theoretical, ideal speedup of 12.
3x for our platform. The results are given in Table  V. We measure only counting time instead of overall execution time because it is the metric used in  [Thoni and Strey 2009]. The actual average speedup is 9. 6x, which is lower than the ideal speedup. This is because for the last iterations of the Apriori algorithm, the number of candidates is lower than the number of counting units, so the FPGA is under-utilized. Actually the datasets used are very small and this effect would have a much lower impact with larger ones. However if considering only the number of passes, the average speedup should be only 7. 1x, but our speedup is higher than that. This is partly due to our transaction de-duplication technique, which reduces the dataset size by 11% to 12%. The low amount of details given in  [Thoni and Strey 2009]  makes it difficult to explain where the rest comes from, but it may be due to our design allowing to simultaneously read the support counters and send another batch of candidates.
It is also pertinent to compare the resource usage and the functionalities of the proposed counting units. Unfortunately in  [Thoni and Strey 2009]  and  [Baker and Prasanna 2006] , neither the counter width nor the maximum itemset size are given. Similarly in  [Baker and Prasanna 2005]  the counter width is not given. As previously shown in section 4. 5 these parameters have a strong impact on the size of counting units, which makes the comparison difficult. Our placement template (see section 4. 5) is 5 slices high, which means 40 LUT6 per counting unit. This is a 29. 2% improvement compared to the best case 56. 5 LUT6 achieved in  [Thoni and Strey 2009]. Using much shorter counters would also be possible with our solution and for instance, for the two datasets used, 15-bit support counters is the minimum that does not require dataset splitting.