source: icGREP/icgrep-devel/icgrep/editd/editd_cpu_kernel.cpp @ 5985

Last change on this file since 5985 was 5985, checked in by nmedfort, 15 months ago

Restructured MultiBlock? kernel. Removal of Swizzled buffers. Inclusion of PopCount? rates / non-linear access. Modifications to several kernels to better align them with the kernel and pipeline changes.

File size: 5.1 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
6#include "editd_cpu_kernel.h"
7#include <kernels/kernel_builder.h>
8#include <llvm/IR/Module.h>
9
10using namespace llvm;
11
12namespace kernel {
13
14void editdCPUKernel::bitblock_advance_ci_co(const std::unique_ptr<kernel::KernelBuilder> & idb,
15                                            Value * val, unsigned shift, Value * stideCarryArr, unsigned carryIdx,
16                                            std::vector<std::vector<Value *>> & adv,
17                                            std::vector<std::vector<int>> & calculated, int i, int j) const {
18    if (calculated[i][j] == 0) {
19        Value * ptr = idb->CreateGEP(stideCarryArr, {idb->getInt32(0), idb->getInt32(carryIdx)});
20        Value * ci = idb->CreateLoad(ptr);
21        std::pair<Value *, Value *> rslt = idb->bitblock_advance(val, ci, shift);
22        idb->CreateStore(std::get<0>(rslt), ptr);
23        adv[i][j] = std::get<1>(rslt);
24        calculated[i][j] = 1;
25    }
26}
27
28void editdCPUKernel::reset_to_zero(std::vector<std::vector<int>> & calculated){
29    for (auto & sub : calculated) {
30        std::fill(sub.begin(), sub.end(), 0);
31    }
32}
33
34void editdCPUKernel::generateDoBlockMethod(const std::unique_ptr<kernel::KernelBuilder> & idb) {
35
36    Type * const int32ty = idb->getInt32Ty();
37    Type * const int8ty = idb->getInt8Ty();
38
39    Value * pattStartPtr = idb->getScalarField("pattStream");
40    Value * strideCarryArr = idb->getScalarField("strideCarry");
41
42    unsigned carryIdx = 0;
43
44    std::vector<std::vector<Value *>> e(mPatternLen + 1, std::vector<Value *>(mEditDistance + 1));
45    std::vector<std::vector<Value *>> adv(mPatternLen, std::vector<Value *>(mEditDistance + 1));
46    std::vector<std::vector<int>> calculated(mPatternLen, std::vector<int>(mEditDistance + 1, 0));
47    Value * pattPos = idb->getInt32(0);
48    for(unsigned j = 0; j <= mEditDistance; j++){
49        e[mPatternLen][j] = idb->allZeroes();
50    }
51
52    for(unsigned j = 1; j <= mEditDistance; j++){
53        e[0][j] = idb->allOnes();
54    }
55
56    for(unsigned g = 0; g < mGroupSize; g++){
57        Value * pattCh = idb->CreateLoad(idb->CreateGEP(pattStartPtr, pattPos));
58        Value * pattIdx = idb->CreateAnd(idb->CreateLShr(pattCh, 1), ConstantInt::get(int8ty, 3));
59        Value * pattStream = idb->loadInputStreamBlock("CCStream", idb->CreateZExt(pattIdx, int32ty));
60        pattPos = idb->CreateAdd(pattPos, ConstantInt::get(int32ty, 1));
61       
62        e[0][0] = pattStream;
63        for(unsigned i = 1; i < mPatternLen; i++){
64            pattCh = idb->CreateLoad(idb->CreateGEP(pattStartPtr, pattPos));
65            pattIdx = idb->CreateAnd(idb->CreateLShr(pattCh, 1), ConstantInt::get(int8ty, 3));
66            pattStream = idb->loadInputStreamBlock("CCStream", idb->CreateZExt(pattIdx, int32ty));
67            pattPos = idb->CreateAdd(pattPos, ConstantInt::get(int32ty, 1));
68            bitblock_advance_ci_co(idb, e[i-1][0], 1, strideCarryArr, carryIdx++, adv, calculated, i-1, 0);
69            e[i][0] = idb->CreateAnd(adv[i-1][0], pattStream);
70            for(unsigned j = 1; j<= mEditDistance; j++){
71                bitblock_advance_ci_co(idb, e[i-1][j], 1, strideCarryArr, carryIdx++, adv, calculated, i-1, j);
72                bitblock_advance_ci_co(idb, e[i-1][j-1], 1, strideCarryArr, carryIdx++, adv, calculated, i-1, j-1);
73                bitblock_advance_ci_co(idb, e[i][j-1], 1, strideCarryArr, carryIdx++, adv, calculated, i, j-1);
74                Value * tmp1 = idb->CreateAnd(adv[i-1][j], pattStream);
75                Value * tmp2 = idb->CreateAnd(adv[i-1][j-1], idb->CreateNot(pattStream));
76                Value * tmp3 = idb->CreateOr(adv[i][j-1], e[i-1][j-1]);
77                e[i][j] = idb->CreateOr(idb->CreateOr(tmp1, tmp2), tmp3);
78            }
79        }
80        e[mPatternLen][0] = idb->CreateOr(e[mPatternLen][0], e[mPatternLen-1][0]);
81        for(unsigned j = 1; j<= mEditDistance; j++){
82            e[mPatternLen][j] = idb->CreateOr(e[mPatternLen][j], idb->CreateAnd(e[mPatternLen - 1][j], idb->CreateNot(e[mPatternLen - 1][j - 1])));
83        }
84        reset_to_zero(calculated);
85    }
86
87    for(unsigned j = 0; j<= mEditDistance; j++){
88        idb->storeOutputStreamBlock("ResultStream", idb->getInt32(j), e[mPatternLen][j]);
89    }
90}
91
92void editdCPUKernel::generateFinalBlockMethod(const std::unique_ptr<KernelBuilder> & idb, Value * remainingBytes) {
93    idb->setScalarField("EOFmask", idb->bitblock_mask_from(remainingBytes));
94    CreateDoBlockMethodCall(idb);
95}
96
97editdCPUKernel::editdCPUKernel(const std::unique_ptr<kernel::KernelBuilder> & b, unsigned dist, unsigned pattLen, unsigned groupSize) :
98BlockOrientedKernel("editd_cpu",
99             {Binding{b->getStreamSetTy(4), "CCStream"}},
100             {Binding{b->getStreamSetTy(dist + 1), "ResultStream"}},
101             {Binding{PointerType::get(b->getInt8Ty(), 1), "pattStream"},
102             Binding{PointerType::get(ArrayType::get(b->getBitBlockType(), pattLen * (dist + 1) * 4 * groupSize), 0), "strideCarry"}},
103             {},
104             {Binding{b->getBitBlockType(), "EOFmask"}}),
105mEditDistance(dist),
106mPatternLen(pattLen),
107mGroupSize(groupSize){
108}
109
110}
111
112
Note: See TracBrowser for help on using the repository browser.