source: icGREP/icgrep-devel/icgrep/editd/editd.cpp @ 5603

Last change on this file since 5603 was 5603, checked in by lindanl, 23 months ago

editd:group pattern segments.

  • Property svn:executable set to *
File size: 32.5 KB
Line 
1/*
2 *  Copyright (c) 2015 International Characters.
3 *  This software is licensed to the public under the Open Software License 3.0.
4 *  icgrep is a trademark of International Characters.
5 */
6
7#include <string>
8#include <iostream>
9#include <fstream>
10#include <toolchain/toolchain.h>
11#include <pablo/pablo_toolchain.h>
12#include <llvm/IR/Function.h>
13#include <llvm/IR/Module.h>
14#include <llvm/Support/CommandLine.h>
15#include <cc/cc_compiler.h>
16#include <pablo/pablo_compiler.h>
17#include <pablo/pablo_kernel.h>
18#include <kernels/kernel_builder.h>
19#include <IR_Gen/idisa_target.h>
20#include <kernels/streamset.h>
21#include <kernels/source_kernel.h>
22#include <kernels/s2p_kernel.h>
23#include <kernels/cc_kernel.h>
24#include <editd/editdscan_kernel.h>
25#include <kernels/streams_merge.h>
26#include <editd/pattern_compiler.h>
27#include <toolchain/cpudriver.h>
28#include <sys/stat.h>
29#include <fcntl.h>
30#include <mutex>
31#include <boost/uuid/sha1.hpp>
32#include <editd/editd_cpu_kernel.h>
33
34#include <toolchain/NVPTXDriver.h>
35#include <editd/editd_gpu_kernel.h>
36#ifdef CUDA_ENABLED
37#include <editd/EditdCudaDriver.h>
38#endif
39
40using namespace llvm;
41
42static cl::list<std::string> inputFiles(cl::Positional, cl::desc("<regex> <input file ...>"), cl::OneOrMore);
43
44static cl::list<std::string> pattVector("e", cl::desc("pattern"), cl::ZeroOrMore);
45static cl::opt<std::string> PatternFilename("f", cl::desc("Take patterns (one per line) from a file"), cl::value_desc("regex file"), cl::init(""));
46
47static cl::opt<bool> CaseInsensitive("i", cl::desc("Ignore case distinctions in the pattern and the file."));
48
49static cl::opt<int> editDistance("edit-dist", cl::desc("Edit Distance Value"), cl::init(2));
50static cl::opt<int> optPosition("opt-pos", cl::desc("Optimize position"), cl::init(0));
51static cl::opt<int> stepSize("step-size", cl::desc("Step Size"), cl::init(3));
52static cl::opt<int> prefixLen("prefix", cl::desc("Prefix length"), cl::init(3));
53static cl::opt<int> groupSize("groupPatterns", cl::desc("Number of pattern segments per group."), cl::init(1));
54static cl::opt<bool> ShowPositions("display", cl::desc("Display the match positions."), cl::init(false));
55
56static cl::opt<int> Threads("threads", cl::desc("Total number of threads."), cl::init(1));
57
58static cl::opt<bool> MultiEditdKernels("enable-multieditd-kernels", cl::desc("Construct multiple editd kernels in one pipeline."));
59static cl::opt<bool> EditdIndexPatternKernels("enable-index-kernels", cl::desc("Use pattern index method."));
60
61using namespace kernel;
62using namespace pablo;
63using namespace parabix;
64
65const static std::string PTXFilename = "editd.ptx";
66
67struct matchPosition
68{
69    size_t pos;
70    size_t dist;
71};
72
73std::vector<struct matchPosition> matchList;
74std::vector<std::vector<std::string>> pattGroups;
75
76void run_second_filter(int pattern_segs, int total_len, float errRate){
77
78    if(matchList.empty()) return;
79
80    //Sort match position
81    bool exchanged = true;
82    while(exchanged){
83        exchanged = false;
84        for (unsigned i=0; i<matchList.size()-1; i++){
85            if(matchList[i].pos > matchList[i+1].pos){
86                size_t tmp_pos = matchList[i].pos;
87                size_t tmp_dist = matchList[i].dist;
88                matchList[i].pos = matchList[i+1].pos;
89                matchList[i].dist = matchList[i+1].dist;
90                matchList[i+1].pos = tmp_pos;
91                matchList[i+1].dist = tmp_dist;
92                exchanged = true;
93            }
94        }
95    }
96
97    //remove the duplicates
98    bool cleared = true;
99    while(cleared){
100        cleared = false;
101        for (unsigned i=0; i<matchList.size()-1; i++){
102            if(matchList[i].pos == matchList[i+1].pos && matchList[i].dist == matchList[i+1].dist){
103                matchList.erase(matchList.begin() + i);
104                cleared = true;
105            }
106        }
107    }
108
109    std::cout << "pattern_segs = " << pattern_segs << ", total_len = " << total_len << std::endl;
110
111    int v = pattern_segs * (editDistance+1) - total_len * errRate;
112
113    int startPos = matchList[0].pos;
114    int sum = matchList[0].dist;
115    int curIdx = 0;
116    unsigned i = 0;
117    int count = 0;
118    while (i < matchList.size()){
119        if(matchList[i].pos - startPos < total_len * (errRate+1)){
120            sum += matchList[i].dist;
121            i++;
122        }
123        else{
124            if(sum > v) count++;
125            sum -= matchList[curIdx].dist;
126            curIdx++;
127            startPos = matchList[curIdx].pos;
128        }
129    }
130
131    std::cout << "total candidate from the first filter is " << matchList.size() << std::endl;
132    std::cout << "total candidate from the second filter is " << count << std::endl;
133}
134
135void get_editd_pattern(int & pattern_segs, int & total_len) {
136
137    if (PatternFilename != "") {
138        std::ifstream pattFile(PatternFilename.c_str());
139        std::string r;
140        if (pattFile.is_open()) {
141            while (std::getline(pattFile, r)) {
142                pattVector.push_back(r);
143                pattern_segs ++;
144                total_len += r.size();
145            }
146            std::sort(pattVector.begin(), pattVector.end());
147            unsigned i = 0;
148            while(i < pattVector.size()){
149                std::vector<std::string> pattGroup;
150                std::string prefix = pattVector[i].substr(0, prefixLen);
151                while(i < pattVector.size() && pattVector[i].substr(0, prefixLen) == prefix){
152                    pattGroup.push_back(pattVector[i]);
153                    i++;
154                }
155                pattGroups.push_back(pattGroup);
156            }
157            pattFile.close();
158        }
159        codegen::GroupNum = pattVector.size()/groupSize;
160    }
161
162    // if there are no regexes specified through -e or -f, the first positional argument
163    // must be a regex, not an input file.
164
165    if (pattVector.size() == 0) {
166        pattVector.push_back(inputFiles[0]);
167        inputFiles.erase(inputFiles.begin());
168    }
169}
170
171inline static std::string sha1sum(const std::string & str) {
172    char buffer[41];    // 40 hex-digits and the terminating null
173    uint32_t digest[5]; // 160 bits in total
174    boost::uuids::detail::sha1 sha1;
175    sha1.process_bytes(str.c_str(), str.size());
176    sha1.get_digest(digest);
177    snprintf(buffer, sizeof(buffer), "%.8x%.8x%.8x%.8x%.8x",
178             digest[0], digest[1], digest[2], digest[3], digest[4]);
179    return std::string(buffer);
180}
181
182std::string createName(const std::vector<std::string> & patterns) {
183    std::string name = "";
184    for(unsigned i=0; i<patterns.size(); i++)
185        name += patterns[i];
186    return name + std::to_string(editDistance);
187}
188
189class PatternKernel final: public pablo::PabloKernel {
190public:
191    PatternKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const std::vector<std::string> & patterns);
192    std::string makeSignature(const std::unique_ptr<kernel::KernelBuilder> & iBuilder) override;
193    bool isCachable() const override { return true;}
194protected:
195    void generatePabloMethod() override;
196private:
197    const std::vector<std::string> & mPatterns;
198};
199
200PatternKernel::PatternKernel(const std::unique_ptr<kernel::KernelBuilder> & b, const std::vector<std::string> & patterns)
201: PabloKernel(b, sha1sum(createName(patterns)), {{b->getStreamSetTy(4), "pat"}}, {{b->getStreamSetTy(editDistance + 1), "E"}})
202, mPatterns(patterns) { 
203}
204
205std::string PatternKernel::makeSignature(const std::unique_ptr<kernel::KernelBuilder> &) {
206    return getName();
207}
208
209void PatternKernel::generatePabloMethod() {
210    PabloBuilder entry(getEntryBlock());
211    Var * const pat = getInputStreamVar("pat");
212    PabloAST * basisBits[4];
213    basisBits[0] = entry.createExtract(pat, 0, "A");
214    basisBits[1] = entry.createExtract(pat, 1, "C");
215    basisBits[2] = entry.createExtract(pat, 2, "T");
216    basisBits[3] = entry.createExtract(pat, 3, "G");
217    re::Pattern_Compiler pattern_compiler(*this);
218    if (optPosition == 0) optPosition = editDistance + 6;
219    pattern_compiler.compile(mPatterns, entry, basisBits, editDistance, optPosition, stepSize);
220}
221
222std::mutex store_mutex;
223void wrapped_report_pos(size_t match_pos, int dist) {
224    struct matchPosition curMatch;
225    curMatch.pos = match_pos;
226    curMatch.dist = dist;
227
228    store_mutex.lock();
229    matchList.push_back(curMatch);
230    if(ShowPositions)
231        std::cout << "pos: " << match_pos << ", dist:" << dist << "\n";
232    store_mutex.unlock();
233}
234
235void editdPipeline(ParabixDriver & pxDriver, const std::vector<std::string> & patterns) {
236
237    auto & idb = pxDriver.getBuilder();
238    Module * const m = idb->getModule();
239    Type * const sizeTy = idb->getSizeTy();
240    Type * const voidTy = idb->getVoidTy();
241    Type * const inputType = PointerType::get(ArrayType::get(ArrayType::get(idb->getBitBlockType(), 8), 1), 0);
242
243    idb->LinkFunction("wrapped_report_pos", &wrapped_report_pos);
244
245    const unsigned segmentSize = codegen::SegmentSize;
246    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
247
248    Function * const main = cast<Function>(m->getOrInsertFunction("Main", voidTy, inputType, sizeTy, nullptr));
249    main->setCallingConv(CallingConv::C);
250    auto args = main->arg_begin();
251    Value * const inputStream = &*(args++);
252    inputStream->setName("input");
253    Value * const fileSize = &*(args++);
254    fileSize->setName("fileSize");
255    idb->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry", main,0));
256
257    auto ChStream = pxDriver.addBuffer(make_unique<SourceBuffer>(idb, idb->getStreamSetTy(4)));
258    auto mmapK = pxDriver.addKernelInstance(make_unique<MemorySourceKernel>(idb, inputType, segmentSize));
259    mmapK->setInitialArguments({inputStream, fileSize});
260    pxDriver.makeKernelCall(mmapK, {}, {ChStream});
261
262    auto MatchResults = pxDriver.addBuffer(make_unique<CircularBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments));
263    auto editdk = pxDriver.addKernelInstance(make_unique<PatternKernel>(idb, patterns));
264    pxDriver.makeKernelCall(editdk, {ChStream}, {MatchResults});
265
266    auto editdScanK = pxDriver.addKernelInstance(make_unique<editdScanKernel>(idb, editDistance));
267    pxDriver.makeKernelCall(editdScanK, {MatchResults}, {});
268
269    pxDriver.generatePipelineIR();
270    pxDriver.deallocateBuffers();
271    idb->CreateRetVoid();
272
273    pxDriver.finalizeObject();
274}
275
276class PreprocessKernel final: public pablo::PabloKernel {
277public:
278    PreprocessKernel(const std::unique_ptr<kernel::KernelBuilder> & b);
279    bool isCachable() const override { return true; }
280    bool hasSignature() const override { return false; }
281protected:
282    void generatePabloMethod() override;
283};
284
285PreprocessKernel::PreprocessKernel(const std::unique_ptr<kernel::KernelBuilder> & b)
286: PabloKernel(b, "ccc", {{b->getStreamSetTy(8), "basis"}}, {{b->getStreamSetTy(4), "pat"}}) {
287
288}
289
290void PreprocessKernel::generatePabloMethod() {
291    cc::CC_Compiler ccc(this, getInputStreamVar("basis"));
292    PabloBuilder & pb = ccc.getBuilder();
293    PabloAST * A = ccc.compileCC(re::makeCC(re::makeCC(0x41), re::makeCC(0x61)), pb);
294    PabloAST * C = ccc.compileCC(re::makeCC(re::makeCC(0x43), re::makeCC(0x63)), pb);
295    PabloAST * T = ccc.compileCC(re::makeCC(re::makeCC(0x54), re::makeCC(0x74)), pb);
296    PabloAST * G = ccc.compileCC(re::makeCC(re::makeCC(0x47), re::makeCC(0x67)), pb);
297    Var * const pat = getOutputStreamVar("pat");
298    pb.createAssign(pb.createExtract(pat, 0), A);
299    pb.createAssign(pb.createExtract(pat, 1), C);
300    pb.createAssign(pb.createExtract(pat, 2), T);
301    pb.createAssign(pb.createExtract(pat, 3), G);
302}
303
304void preprocessPipeline(ParabixDriver & pxDriver) {
305
306    auto & iBuilder = pxDriver.getBuilder();
307    Module * m = iBuilder->getModule();
308
309    Type * const voidTy = iBuilder->getVoidTy();
310    Type * const int32Ty = iBuilder->getInt32Ty();
311    Type * const outputType = PointerType::get(ArrayType::get(iBuilder->getBitBlockType(), 4), 0);
312
313    const unsigned segmentSize = codegen::SegmentSize;
314    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
315
316    Function * const main = cast<Function>(m->getOrInsertFunction("Main", voidTy, int32Ty, outputType, nullptr));
317    main->setCallingConv(CallingConv::C);
318    Function::arg_iterator args = main->arg_begin();
319
320    Value * const fileDescriptor = &*(args++);
321    fileDescriptor->setName("fileDescriptor");
322    Value * const outputStream = &*(args++);
323    outputStream->setName("output");
324
325    iBuilder->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry", main));
326
327    auto ByteStream = pxDriver.addBuffer(make_unique<SourceBuffer>(iBuilder, iBuilder->getStreamSetTy(1, 8)));
328
329    auto mmapK = pxDriver.addKernelInstance(make_unique<MMapSourceKernel>(iBuilder, segmentSize));
330    mmapK->setInitialArguments({fileDescriptor});
331    pxDriver.makeKernelCall(mmapK, {}, {ByteStream});
332
333    auto BasisBits = pxDriver.addBuffer(make_unique<CircularBuffer>(iBuilder, iBuilder->getStreamSetTy(8), segmentSize * bufferSegments));
334    auto s2pk = pxDriver.addKernelInstance(make_unique<S2PKernel>(iBuilder));
335    pxDriver.makeKernelCall(s2pk, {ByteStream}, {BasisBits});
336
337    auto CCResults = pxDriver.addExternalBuffer(make_unique<ExternalBuffer>(iBuilder, iBuilder->getStreamSetTy(4), outputStream));
338    auto ccck = pxDriver.addKernelInstance(make_unique<PreprocessKernel>(iBuilder));
339    pxDriver.makeKernelCall(ccck, {BasisBits}, {CCResults});
340
341    pxDriver.generatePipelineIR();
342    pxDriver.deallocateBuffers();
343    iBuilder->CreateRetVoid();
344
345    pxDriver.finalizeObject();
346}
347
348void multiEditdPipeline(ParabixDriver & pxDriver) {
349    auto & idb = pxDriver.getBuilder();
350    Module * const m = idb->getModule();
351    Type * const voidTy = idb->getVoidTy();
352    Type * const int32Ty = idb->getInt32Ty();
353
354    idb->LinkFunction("wrapped_report_pos", &wrapped_report_pos);
355
356    const unsigned segmentSize = codegen::SegmentSize;
357    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
358
359    Function * const main = cast<Function>(m->getOrInsertFunction("Main", voidTy, int32Ty, nullptr));
360    main->setCallingConv(CallingConv::C);
361    Function::arg_iterator args = main->arg_begin();
362
363    Value * const fileDescriptor = &*(args++);
364    fileDescriptor->setName("fileDescriptor");
365
366    idb->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry", main,0));
367
368    auto ByteStream = pxDriver.addBuffer(make_unique<SourceBuffer>(idb, idb->getStreamSetTy(1, 8)));
369
370    auto mmapK = pxDriver.addKernelInstance(make_unique<MMapSourceKernel>(idb, segmentSize));
371    mmapK->setInitialArguments({fileDescriptor});
372    pxDriver.makeKernelCall(mmapK, {}, {ByteStream});
373
374    auto ChStream = pxDriver.addBuffer(make_unique<CircularBuffer>(idb, idb->getStreamSetTy(4), segmentSize * bufferSegments));
375    auto ccck = pxDriver.addKernelInstance(make_unique<kernel::DirectCharacterClassKernelBuilder>(idb, "ccc", 
376        std::vector<re::CC *>{re::makeCC(re::makeCC(0x41), re::makeCC(0x61)),
377                              re::makeCC(re::makeCC(0x43), re::makeCC(0x63)),
378                              re::makeCC(re::makeCC(0x54), re::makeCC(0x74)),
379                              re::makeCC(re::makeCC(0x47), re::makeCC(0x67))}, 1));
380    pxDriver.makeKernelCall(ccck, {ByteStream}, {ChStream});
381
382    const auto n = pattGroups.size();
383   
384    std::vector<StreamSetBuffer *> MatchResultsBufs(n);
385   
386    for(unsigned i = 0; i < n; ++i){
387        auto MatchResults = pxDriver.addBuffer(make_unique<CircularBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments));
388        auto editdk = pxDriver.addKernelInstance(make_unique<PatternKernel>(idb, pattGroups[i]));
389        pxDriver.makeKernelCall(editdk, {ChStream}, {MatchResults});
390        MatchResultsBufs[i] = MatchResults;
391    }
392    StreamSetBuffer * MergedResults = MatchResultsBufs[0];
393    if (n > 1) {
394        MergedResults = pxDriver.addBuffer(make_unique<CircularBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments));
395        kernel::Kernel * streamsMergeK = pxDriver.addKernelInstance(make_unique<kernel::StreamsMerge>(idb, editDistance + 1, n));
396        pxDriver.makeKernelCall(streamsMergeK, MatchResultsBufs, {MergedResults});
397    }
398
399    auto editdScanK = pxDriver.addKernelInstance(make_unique<editdScanKernel>(idb, editDistance));
400    pxDriver.makeKernelCall(editdScanK, {MergedResults}, {});
401
402    pxDriver.generatePipelineIR();
403    pxDriver.deallocateBuffers();
404    idb->CreateRetVoid();
405
406    pxDriver.finalizeObject();
407}
408
409
410void editdIndexPatternPipeline(ParabixDriver & pxDriver, unsigned patternLen) {
411
412    auto & idb = pxDriver.getBuilder();
413    Module * const m = idb->getModule();
414    Type * const sizeTy = idb->getSizeTy();
415    Type * const voidTy = idb->getVoidTy();
416    Type * const inputType = PointerType::get(ArrayType::get(ArrayType::get(idb->getBitBlockType(), 8), 1), 0);
417    Type * const patternPtrTy = PointerType::get(idb->getInt8Ty(), 0);
418
419    idb->LinkFunction("wrapped_report_pos", &wrapped_report_pos);
420
421    const unsigned segmentSize = codegen::SegmentSize;
422    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
423
424    Function * const main = cast<Function>(m->getOrInsertFunction("Main", voidTy, inputType, sizeTy, patternPtrTy, nullptr));
425    main->setCallingConv(CallingConv::C);
426    auto args = main->arg_begin();
427    Value * const inputStream = &*(args++);
428    inputStream->setName("input");
429    Value * const fileSize = &*(args++);
430    fileSize->setName("fileSize");
431    Value * const pattStream = &*(args++);
432    pattStream->setName("pattStream");
433    idb->SetInsertPoint(BasicBlock::Create(m->getContext(), "entry", main,0));
434
435    auto ChStream = pxDriver.addBuffer(make_unique<SourceBuffer>(idb, idb->getStreamSetTy(4)));
436    auto mmapK = pxDriver.addKernelInstance(make_unique<MemorySourceKernel>(idb, inputType, segmentSize));
437    mmapK->setInitialArguments({inputStream, fileSize});
438    pxDriver.makeKernelCall(mmapK, {}, {ChStream});
439
440    auto MatchResults = pxDriver.addBuffer(make_unique<CircularBuffer>(idb, idb->getStreamSetTy(editDistance + 1), segmentSize * bufferSegments));
441    auto editdk = pxDriver.addKernelInstance(make_unique<kernel::editdCPUKernel>(idb, editDistance, patternLen, groupSize));
442
443    const unsigned numOfCarries = patternLen * (editDistance + 1) * 4 * groupSize;
444    Type * strideCarryTy = ArrayType::get(idb->getBitBlockType(), numOfCarries);
445    Value * strideCarry = idb->CreateAlloca(strideCarryTy);
446    idb->CreateStore(Constant::getNullValue(strideCarryTy), strideCarry);
447
448    editdk->setInitialArguments({pattStream, strideCarry});
449    pxDriver.makeKernelCall(editdk, {ChStream}, {MatchResults});
450
451    auto editdScanK = pxDriver.addKernelInstance(make_unique<editdScanKernel>(idb, editDistance));
452    pxDriver.makeKernelCall(editdScanK, {MatchResults}, {});
453
454    pxDriver.generatePipelineIR();
455
456    idb->CreateRetVoid();
457
458    pxDriver.finalizeObject();
459}
460
461typedef void (*preprocessFunctionType)(const int fd, char * output_data);
462
463typedef void (*editdFunctionType)(char * byte_data, size_t filesize);
464
465typedef void (*multiEditdFunctionType)(const int fd);
466
467typedef void (*editdIndexFunctionType)(char * byte_data, size_t filesize, const char * pattern);
468
469static char * chStream;
470static size_t size;
471
472size_t file_size(const int fd) {
473    struct stat st;
474    if (LLVM_UNLIKELY(fstat(fd, &st) != 0)) {
475        st.st_size = 0;
476    }
477    return st.st_size;
478}
479
480char * preprocess(preprocessFunctionType fn_ptr) {
481    std::string fileName = inputFiles[0];
482    const int fd = open(inputFiles[0].c_str(), O_RDONLY);
483    if (LLVM_UNLIKELY(fd == -1)) {
484        std::cerr << "Error: cannot open " << fileName << " for processing. Skipped.\n";
485        exit(-1);
486    }
487    size = file_size(fd);
488    int ret = posix_memalign((void**)&chStream, 32, size);
489    if (ret) {
490        std::cerr << "Cannot allocate memory for output.\n";
491        exit(-2);
492    }
493    fn_ptr(fd, chStream);
494    close(fd);
495    return chStream;
496}
497
498void editd(editdFunctionType fn_ptr, char * inputStream, size_t size) {
499    fn_ptr(inputStream, size);
500}
501
502std::mutex count_mutex;
503size_t groupCount;
504void * DoEditd(void *)
505{
506    size_t groupIdx;
507    count_mutex.lock();
508    groupIdx = groupCount;
509    groupCount++;
510    count_mutex.unlock();
511
512    while (groupIdx < pattGroups.size()){
513
514        ParabixDriver pxDriver("editd");
515        editdPipeline(pxDriver, pattGroups[groupIdx]);
516        auto editd_ptr = reinterpret_cast<editdFunctionType>(pxDriver.getMain());
517        editd(editd_ptr, chStream, size);
518
519        count_mutex.lock();
520        groupIdx = groupCount;
521        groupCount++;
522        count_mutex.unlock();
523    }
524
525    pthread_exit(NULL);
526}
527
528void editdGPUCodeGen(unsigned patternLen){
529    NVPTXDriver pxDriver("editd");
530    auto & iBuilder = pxDriver.getBuilder();
531    Module * M = iBuilder->getModule();
532
533    const unsigned segmentSize = codegen::SegmentSize;
534
535    Type * const mBitBlockType = iBuilder->getBitBlockType();
536    Type * const inputSizeTy = PointerType::get(iBuilder->getSizeTy(), 1);
537    Type * const int32ty = iBuilder->getInt32Ty();
538    Type * const voidTy = Type::getVoidTy(M->getContext());
539    Type * const inputTy = PointerType::get(ArrayType::get(mBitBlockType, 4), 1);
540    Type * const patternPtrTy = PointerType::get(iBuilder->getInt8Ty(), 1);
541    Type * const outputTy = PointerType::get(ArrayType::get(mBitBlockType, editDistance+1), 1);
542    Type * const stridesTy = PointerType::get(int32ty, 1);
543
544    Function * const main = cast<Function>(M->getOrInsertFunction("Main", voidTy, inputTy, inputSizeTy, patternPtrTy, outputTy, stridesTy, nullptr));
545    main->setCallingConv(CallingConv::C);
546    Function::arg_iterator args = main->arg_begin();
547
548    Value * const inputStream = &*(args++);
549    inputStream->setName("input");
550    Value * const inputSizePtr = &*(args++);
551    inputSizePtr->setName("inputSizePtr");
552    Value * const pattStream = &*(args++);
553    pattStream->setName("pattStream");
554    Value * const resultStream = &*(args++);
555    resultStream->setName("resultStream");
556    Value * const stridesPtr = &*(args++);
557    stridesPtr->setName("stridesPtr");
558
559    iBuilder->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", main,0));
560
561    Function * tidFunc = M->getFunction("llvm.nvvm.read.ptx.sreg.tid.x");
562    Value * tid = iBuilder->CreateCall(tidFunc);
563    Function * bidFunc = cast<Function>(M->getOrInsertFunction("llvm.nvvm.read.ptx.sreg.ctaid.x", int32ty, nullptr));
564    Value * bid = iBuilder->CreateCall(bidFunc);
565
566    Value * inputThreadPtr = iBuilder->CreateGEP(inputStream, tid);
567    Value * strides = iBuilder->CreateLoad(stridesPtr);
568    Value * outputBlocks = iBuilder->CreateMul(strides, ConstantInt::get(int32ty, iBuilder->getStride() / iBuilder->getBitBlockWidth()));
569    Value * resultStreamPtr = iBuilder->CreateGEP(resultStream, iBuilder->CreateAdd(iBuilder->CreateMul(bid, outputBlocks), tid));
570    Value * inputSize = iBuilder->CreateLoad(inputSizePtr);
571
572    StreamSetBuffer * CCStream = pxDriver.addBuffer(make_unique<SourceBuffer>(iBuilder, iBuilder->getStreamSetTy(4), 1));
573    kernel::Kernel * sourceK = pxDriver.addKernelInstance(make_unique<kernel::MemorySourceKernel>(iBuilder, inputTy, segmentSize));
574    sourceK->setInitialArguments({inputThreadPtr, inputSize});
575    pxDriver.makeKernelCall(sourceK, {}, {CCStream});
576
577    ExternalBuffer * ResultStream = pxDriver.addExternalBuffer(make_unique<ExternalBuffer>(iBuilder, iBuilder->getStreamSetTy(editDistance+1), resultStreamPtr, 1));   
578    kernel::Kernel * editdk = pxDriver.addKernelInstance(make_unique<kernel::editdGPUKernel>(iBuilder, editDistance, patternLen, groupSize));
579     
580    const unsigned numOfCarries = patternLen * (editDistance + 1) * 4 * groupSize;
581    Type * strideCarryTy = ArrayType::get(mBitBlockType, numOfCarries);
582    Value * strideCarry = iBuilder->CreateAlloca(strideCarryTy);
583    iBuilder->CreateStore(Constant::getNullValue(strideCarryTy), strideCarry);
584
585    editdk->setInitialArguments({pattStream, strideCarry});
586    pxDriver.makeKernelCall(editdk, {CCStream}, {ResultStream});
587
588    pxDriver.generatePipelineIR();
589    pxDriver.deallocateBuffers();
590    iBuilder->CreateRetVoid();
591
592    pxDriver.finalizeObject();
593
594}
595
596void mergeGPUCodeGen(){
597    NVPTXDriver pxDriver("merge");
598    auto & iBuilder = pxDriver.getBuilder();
599    Module * M = iBuilder->getModule();
600
601    Type * const mBitBlockType = iBuilder->getBitBlockType();
602    Type * const int32ty = iBuilder->getInt32Ty();
603    Type * const voidTy = Type::getVoidTy(M->getContext());
604    Type * const resultTy = PointerType::get(ArrayType::get(mBitBlockType, editDistance+1), 1);
605    Type * const stridesTy = PointerType::get(int32ty, 1);
606
607    Function * const main = cast<Function>(M->getOrInsertFunction("Main", voidTy, resultTy, stridesTy, nullptr));
608    main->setCallingConv(CallingConv::C);
609    Function::arg_iterator args = main->arg_begin();
610
611    Value * const resultStream = &*(args++);
612    resultStream->setName("resultStream");
613    Value * const stridesPtr = &*(args++);
614    stridesPtr->setName("stridesPtr");
615
616    BasicBlock * entryBlock = BasicBlock::Create(iBuilder->getContext(), "entryBlock", main, 0);
617    BasicBlock * strideLoopCond = BasicBlock::Create(iBuilder->getContext(), "strideLoopCond", main, 0);
618    BasicBlock * strideLoopBody = BasicBlock::Create(iBuilder->getContext(), "strideLoopBody", main, 0);
619    BasicBlock * stridesDone = BasicBlock::Create(iBuilder->getContext(), "stridesDone", main, 0);
620
621    iBuilder->SetInsertPoint(entryBlock);
622
623    Function * tidFunc = M->getFunction("llvm.nvvm.read.ptx.sreg.tid.x");
624    Value * tid = iBuilder->CreateCall(tidFunc);
625    Function * bidFunc = cast<Function>(M->getOrInsertFunction("llvm.nvvm.read.ptx.sreg.ctaid.x", int32ty, nullptr));
626    Value * bid = iBuilder->CreateCall(bidFunc);
627
628    Value * strides = iBuilder->CreateLoad(stridesPtr);
629    Value * strideBlocks = ConstantInt::get(int32ty, iBuilder->getStride() / iBuilder->getBitBlockWidth());
630    Value * outputBlocks = iBuilder->CreateMul(strides, strideBlocks);
631    Value * resultStreamPtr = iBuilder->CreateGEP(resultStream, tid);
632
633    iBuilder->CreateBr(strideLoopCond);
634    iBuilder->SetInsertPoint(strideLoopCond);
635    PHINode * strideNo = iBuilder->CreatePHI(int32ty, 2, "strideNo");
636    strideNo->addIncoming(ConstantInt::get(int32ty, 0), entryBlock);
637    Value * notDone = iBuilder->CreateICmpULT(strideNo, strides);
638    iBuilder->CreateCondBr(notDone, strideLoopBody, stridesDone);
639
640    iBuilder->SetInsertPoint(strideLoopBody);
641    Value * myResultStreamPtr = iBuilder->CreateGEP(resultStreamPtr, {iBuilder->CreateMul(strideBlocks, strideNo)});
642    Value * myResultStream = iBuilder->CreateLoad(iBuilder->CreateGEP(myResultStreamPtr, {iBuilder->getInt32(0), bid}));
643    for (int i=1; i<codegen::GroupNum; i++){
644        Value * nextStreamPtr = iBuilder->CreateGEP(myResultStreamPtr, {iBuilder->CreateMul(outputBlocks, iBuilder->getInt32(i)), bid});
645        myResultStream = iBuilder->CreateOr(myResultStream, iBuilder->CreateLoad(nextStreamPtr));
646    }
647    iBuilder->CreateStore(myResultStream, iBuilder->CreateGEP(myResultStreamPtr, {iBuilder->getInt32(0), bid}));
648    strideNo->addIncoming(iBuilder->CreateAdd(strideNo, ConstantInt::get(int32ty, 1)), strideLoopBody);
649    iBuilder->CreateBr(strideLoopCond);
650
651    iBuilder->SetInsertPoint(stridesDone);
652    iBuilder->CreateRetVoid();
653
654    pxDriver.finalizeObject();
655
656}
657
658editdFunctionType editdScanCPUCodeGen(ParabixDriver & pxDriver) {
659   
660    auto & iBuilder = pxDriver.getBuilder();
661    Module * M = iBuilder->getModule();
662
663    const unsigned segmentSize = codegen::SegmentSize;
664    const unsigned bufferSegments = codegen::BufferSegments * codegen::ThreadNum;
665
666    Type * mBitBlockType = iBuilder->getBitBlockType();
667    Type * const size_ty = iBuilder->getSizeTy();
668    Type * const voidTy = Type::getVoidTy(M->getContext());
669    Type * const inputType = PointerType::get(ArrayType::get(mBitBlockType, editDistance+1), 0);
670
671    Function * const main = cast<Function>(M->getOrInsertFunction("Main", voidTy, inputType, size_ty, nullptr));
672    main->setCallingConv(CallingConv::C);
673    iBuilder->SetInsertPoint(BasicBlock::Create(M->getContext(), "entry", main, 0));
674    Function::arg_iterator args = main->arg_begin();
675    Value * const inputStream = &*(args++);
676    inputStream->setName("input");
677    Value * const fileSize = &*(args++);
678    fileSize->setName("fileSize");
679
680    StreamSetBuffer * MatchResults = pxDriver.addBuffer(make_unique<SourceBuffer>(iBuilder, iBuilder->getStreamSetTy(editDistance+1)));
681    kernel::Kernel * sourceK = pxDriver.addKernelInstance(make_unique<kernel::MemorySourceKernel>(iBuilder, inputType, segmentSize * bufferSegments));
682    sourceK->setInitialArguments({inputStream, fileSize});
683    pxDriver.makeKernelCall(sourceK, {}, {MatchResults});
684
685    auto editdScanK = pxDriver.addKernelInstance(make_unique<editdScanKernel>(iBuilder, editDistance));
686    pxDriver.makeKernelCall(editdScanK, {MatchResults}, {});
687       
688    pxDriver.generatePipelineIR();
689    pxDriver.deallocateBuffers();
690    iBuilder->CreateRetVoid();
691
692    pxDriver.LinkFunction(*editdScanK, "wrapped_report_pos", &wrapped_report_pos);
693    pxDriver.finalizeObject();
694
695    return reinterpret_cast<editdFunctionType>(pxDriver.getMain());
696
697}
698
699int main(int argc, char *argv[]) {
700    codegen::ParseCommandLineOptions(argc, argv);
701    int pattern_segs = 0;
702    int total_len = 0;
703
704    get_editd_pattern(pattern_segs, total_len);
705
706    if (MultiEditdKernels) {
707        ParabixDriver pxDriver("editd");
708        multiEditdPipeline(pxDriver);
709        auto editd_ptr = reinterpret_cast<multiEditdFunctionType>(pxDriver.getMain());
710
711        std::string fileName = inputFiles[0];
712        const int fd = open(inputFiles[0].c_str(), O_RDONLY);
713        if (LLVM_UNLIKELY(fd == -1)) {
714            std::cerr << "Error: cannot open " << fileName << " for processing. Skipped.\n";
715            exit(-1);
716        }
717        editd_ptr(fd);
718        close(fd);
719        run_second_filter(pattern_segs, total_len, 0.15);
720        return 0;
721    }
722
723#ifdef CUDA_ENABLED
724    if (codegen::NVPTX)
725        codegen::BlockSize = 64;
726#endif
727
728    ParabixDriver pxDriver("preprocess");
729    preprocessPipeline(pxDriver);
730    auto preprocess_ptr = reinterpret_cast<preprocessFunctionType>(pxDriver.getMain());
731    preprocess(preprocess_ptr);
732
733#ifdef CUDA_ENABLED
734    if(codegen::NVPTX){
735
736        std::ifstream t(PatternFilename);
737        if (!t.is_open()) {
738            std::cerr << "Error: cannot open " << PatternFilename << " for processing. Skipped.\n";
739            exit(-1);
740        }
741        std::string patterns((std::istreambuf_iterator<char>(t)), std::istreambuf_iterator<char>());
742
743        editdGPUCodeGen(pattVector[0].length());
744        mergeGPUCodeGen();
745        ulong * rslt = RunPTX(PTXFilename, chStream, size, patterns.c_str(), patterns.length(), editDistance);
746
747        ParabixDriver scanDriver("scan");
748        editdFunctionType editd_ptr = editdScanCPUCodeGen(scanDriver);
749        editd(editd_ptr, (char*)rslt, size);
750
751        run_second_filter(pattern_segs, total_len, 0.15);
752
753        return 0;
754    }
755#endif
756
757    if(pattVector.size() == 1){
758
759        ParabixDriver pxDriver("editd");
760        editdPipeline(pxDriver, pattVector);
761        auto editd_ptr = reinterpret_cast<editdFunctionType>(pxDriver.getMain());
762        editd(editd_ptr, chStream, size);
763        std::cout << "total matches is " << matchList.size() << std::endl;
764    }
765    else{
766        if (Threads == 1) { 
767            if (EditdIndexPatternKernels) {
768                ParabixDriver pxDriver("editd");
769                editdIndexPatternPipeline(pxDriver, pattVector[0].length());
770                auto editd_ptr = reinterpret_cast<editdIndexFunctionType>(pxDriver.getMain());
771
772                for(unsigned i=0; i<pattVector.size(); i+=groupSize){
773                    std::string pattern = "";
774                    for (int j=0; j<groupSize; j++){
775                        pattern += pattVector[i+j];
776                    }
777                    editd_ptr(chStream, size, pattern.c_str());
778                }
779            }
780            else {
781                for(unsigned i=0; i<pattGroups.size(); i++){
782
783                    ParabixDriver pxDriver("editd");
784                    editdPipeline(pxDriver, pattGroups[i]);
785                    auto editd_ptr = reinterpret_cast<editdFunctionType>(pxDriver.getMain());
786                    editd(editd_ptr, chStream, size);
787                }
788            }
789        }
790        else{
791            const unsigned numOfThreads = Threads;
792            pthread_t threads[numOfThreads];
793            groupCount = 0;
794
795            for(unsigned long i = 0; i < numOfThreads; ++i){
796                const int rc = pthread_create(&threads[i], NULL, DoEditd, (void *)i);
797                if (rc) {
798                    llvm::report_fatal_error("Failed to create thread: code " + std::to_string(rc));
799                }
800            }
801
802            for(unsigned i = 0; i < numOfThreads; ++i) {
803                void * status = nullptr;
804                const int rc = pthread_join(threads[i], &status);
805                if (rc) {
806                    llvm::report_fatal_error("Failed to join thread: code " + std::to_string(rc));
807                }
808            }
809
810        }
811        run_second_filter(pattern_segs, total_len, 0.15);
812    }
813
814    return 0;
815}
Note: See TracBrowser for help on using the repository browser.