source: icGREP/icgrep-devel/icgrep/kernels/deletion.h

Last change on this file was 6261, checked in by nmedfort, 7 months ago

Work on OptimizationBranch?; revisited pipeline termination

File size: 5.8 KB
Line 
1/*
2 *  Copyright (c) 2016 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 */
5#ifndef DELETION_H
6#define DELETION_H
7
8#include "kernel.h"
9#include <llvm/IR/Value.h>
10#include <toolchain/driver.h>
11
12namespace IDISA { class IDISA_Builder; }
13
14namespace kernel {
15
16//
17// Parallel Prefix Deletion Kernel
18// see Parallel Prefix Compress in Henry S. Warren, Hacker's Delight, Chapter 7
19//
20// Given that we want to delete bits within fields of width fw, moving
21// nondeleted bits to the right, the parallel prefix compress method can
22// be applied.   This requires a preprocessing step to compute log2(fw)
23// masks that can be used to select bits to be moved in each step of the
24// algorithm.
25//
26class DeletionKernel final : public BlockOrientedKernel {
27public:
28    DeletionKernel(const std::unique_ptr<kernel::KernelBuilder> & b, unsigned fw, unsigned streamCount);
29    bool isCachable() const override { return true; }
30    bool hasSignature() const override { return false; }
31protected:
32    void generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & iBuilder) override;
33    void generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & iBuilder, llvm::Value * remainingBytes) override;
34private:
35    const unsigned mDeletionFieldWidth;
36    const unsigned mStreamCount;
37};
38
39// Compress within fields of size fw.
40class FieldCompressKernel final : public MultiBlockKernel {
41public:
42    FieldCompressKernel(const std::unique_ptr<kernel::KernelBuilder> & b, unsigned fw, StreamSet * inputStreamSet, StreamSet * extractionMask, StreamSet * outputStreamSet);
43    bool isCachable() const override { return true; }
44    bool hasSignature() const override { return false; }
45protected:
46    void generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & kb, llvm::Value * const numOfStrides) override;
47private:
48    const unsigned mCompressFieldWidth;
49    const unsigned mStreamCount;
50};
51
52class PEXTFieldCompressKernel final : public MultiBlockKernel {
53public:
54    PEXTFieldCompressKernel(const std::unique_ptr<kernel::KernelBuilder> & b, unsigned fw, unsigned streamCount);
55    bool isCachable() const override { return true; }
56    bool hasSignature() const override { return false; }
57protected:
58    void generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & kb, llvm::Value * const numOfStrides) override;
59private:
60    const unsigned mPEXTWidth;
61    const unsigned mStreamCount;
62};
63
64//
65//  Given streams that are compressed within fields, produced fully
66//  compressed streams.
67class StreamCompressKernel final : public MultiBlockKernel {
68public:
69    StreamCompressKernel(const std::unique_ptr<kernel::KernelBuilder> & b
70                         , StreamSet * source
71                         , StreamSet * extractionMask
72                         , StreamSet * compressedOutput
73                         , const unsigned FieldWidth = sizeof(size_t) * 8);
74
75    bool isCachable() const override { return true; }
76    bool hasSignature() const override { return false; }
77protected:
78    void generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & kb, llvm::Value * const numOfBlocks) override;
79private:
80    const unsigned mCompressedFieldWidth;
81    const unsigned mStreamCount;
82};
83
84/*
85Input: a set of bitstreams
86Output: swizzles containing the input bitstreams with the specified bits deleted
87*/
88class SwizzledDeleteByPEXTkernel final : public MultiBlockKernel {
89public:
90    using SwizzleSets = std::vector<std::vector<llvm::Value *>>;
91    SwizzledDeleteByPEXTkernel(const std::unique_ptr<kernel::KernelBuilder> & b
92                               , StreamSet * selectors, StreamSet * inputStreamSet
93                               , const std::vector<StreamSet *> & outputs
94                               , unsigned PEXTWidth = sizeof(size_t) * 8);
95    bool isCachable() const override { return true; }
96    bool hasSignature() const override { return false; }
97protected:
98    void generateMultiBlockLogic(const std::unique_ptr<KernelBuilder> & b, llvm::Value * const numOfBlocks) override;
99private:
100    SwizzleSets makeSwizzleSets(const std::unique_ptr<KernelBuilder> & b, llvm::Value * selectors, llvm::Value * const strideIndex);
101private:
102    const unsigned mStreamCount;
103    const unsigned mSwizzleFactor;
104    const unsigned mSwizzleSetCount;
105    const unsigned mPEXTWidth;
106};
107
108class DeleteByPEXTkernel final : public BlockOrientedKernel {
109public:
110    DeleteByPEXTkernel(const std::unique_ptr<kernel::KernelBuilder> & b, unsigned fw, unsigned streamCount, unsigned PEXT_width = sizeof(size_t) * 8);
111    bool isCachable() const override { return true; }
112    bool hasSignature() const override { return false; }
113protected:
114    void generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & iBuilder) override;
115    void generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & iBuilder, llvm::Value * remainingBytes) override;
116    void generateProcessingLoop(const std::unique_ptr<KernelBuilder> & iBuilder, llvm::Value * delMask);
117private:
118    const unsigned mDelCountFieldWidth;
119    const unsigned mStreamCount;
120    const unsigned mSwizzleFactor;
121    const unsigned mPEXTWidth;
122};
123
124class SwizzledBitstreamCompressByCount final : public BlockOrientedKernel {
125public:
126    SwizzledBitstreamCompressByCount(const std::unique_ptr<kernel::KernelBuilder> & b, unsigned bitStreamCount, unsigned fieldWidth = sizeof(size_t) * 8);
127    bool isCachable() const override { return true; }
128    bool hasSignature() const override { return false; }
129protected:
130    void generateDoBlockMethod(const std::unique_ptr<KernelBuilder> & iBuilder) override;
131    void generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & iBuilder, llvm::Value * remainingBytes) override;
132private:
133    const unsigned mBitStreamCount;
134    const unsigned mFieldWidth;
135    const unsigned mSwizzleFactor;
136    const unsigned mSwizzleSetCount;
137};
138
139
140}
141
142#endif
143
Note: See TracBrowser for help on using the repository browser.