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

Last change on this file since 6184 was 6184, checked in by nmedfort, 9 months ago

Initial version of PipelineKernel? + revised StreamSet? model.

  • Property svn:executable set to *
File size: 18.0 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 <editd/editd_cpu_kernel.h>
32#include <kernels/pipeline_builder.h>
33#include <util/aligned_allocator.h>
34
35using namespace llvm;
36
37static cl::list<std::string> inputFiles(cl::Positional, cl::desc("<regex> <input file ...>"), cl::OneOrMore);
38
39static cl::list<std::string> pattVector("e", cl::desc("pattern"), cl::ZeroOrMore);
40static cl::opt<std::string> PatternFilename("f", cl::desc("Take patterns (one per line) from a file"), cl::value_desc("regex file"), cl::init(""));
41
42static cl::opt<bool> CaseInsensitive("i", cl::desc("Ignore case distinctions in the pattern and the file."));
43
44static cl::opt<int> editDistance("edit-dist", cl::desc("Edit Distance Value"), cl::init(2));
45static cl::opt<int> optPosition("opt-pos", cl::desc("Optimize position"), cl::init(0));
46static cl::opt<int> stepSize("step-size", cl::desc("Step Size"), cl::init(3));
47static cl::opt<int> prefixLen("prefix", cl::desc("Prefix length"), cl::init(3));
48static cl::opt<int> groupSize("groupPatterns", cl::desc("Number of pattern segments per group."), cl::init(1));
49static cl::opt<bool> ShowPositions("display", cl::desc("Display the match positions."), cl::init(false));
50
51static cl::opt<int> Threads("threads", cl::desc("Total number of threads."), cl::init(1));
52
53static cl::opt<bool> MultiEditdKernels("enable-multieditd-kernels", cl::desc("Construct multiple editd kernels in one pipeline."));
54static cl::opt<bool> EditdIndexPatternKernels("enable-index-kernels", cl::desc("Use pattern index method."));
55
56using namespace kernel;
57using namespace pablo;
58
59struct matchPosition
60{
61    size_t pos;
62    size_t dist;
63};
64
65std::vector<struct matchPosition> matchList;
66std::vector<std::vector<std::string>> pattGroups;
67
68void run_second_filter(int pattern_segs, int total_len, float errRate){
69
70    if(matchList.empty()) return;
71
72    //Sort match position
73    bool exchanged = true;
74    while(exchanged){
75        exchanged = false;
76        for (unsigned i=0; i<matchList.size()-1; i++){
77            if(matchList[i].pos > matchList[i+1].pos){
78                size_t tmp_pos = matchList[i].pos;
79                size_t tmp_dist = matchList[i].dist;
80                matchList[i].pos = matchList[i+1].pos;
81                matchList[i].dist = matchList[i+1].dist;
82                matchList[i+1].pos = tmp_pos;
83                matchList[i+1].dist = tmp_dist;
84                exchanged = true;
85            }
86        }
87    }
88
89    //remove the duplicates
90    bool cleared = true;
91    while(cleared){
92        cleared = false;
93        for (unsigned i=0; i<matchList.size()-1; i++){
94            if(matchList[i].pos == matchList[i+1].pos && matchList[i].dist == matchList[i+1].dist){
95                matchList.erase(matchList.begin() + i);
96                cleared = true;
97            }
98        }
99    }
100
101    std::cout << "pattern_segs = " << pattern_segs << ", total_len = " << total_len << std::endl;
102
103    int v = pattern_segs * (editDistance+1) - total_len * errRate;
104
105    int startPos = matchList[0].pos;
106    int sum = matchList[0].dist;
107    int curIdx = 0;
108    unsigned i = 0;
109    int count = 0;
110    while (i < matchList.size()){
111        if(matchList[i].pos - startPos < total_len * (errRate+1)){
112            sum += matchList[i].dist;
113            i++;
114        }
115        else{
116            if(sum > v) count++;
117            sum -= matchList[curIdx].dist;
118            curIdx++;
119            startPos = matchList[curIdx].pos;
120        }
121    }
122
123    std::cout << "total candidate from the first filter is " << matchList.size() << std::endl;
124    std::cout << "total candidate from the second filter is " << count << std::endl;
125}
126
127void get_editd_pattern(int & pattern_segs, int & total_len) {
128
129    if (PatternFilename != "") {
130        std::ifstream pattFile(PatternFilename.c_str());
131        std::string r;
132        if (pattFile.is_open()) {
133            while (std::getline(pattFile, r)) {
134                pattVector.push_back(r);
135                pattern_segs ++;
136                total_len += r.size();
137            }
138            std::sort(pattVector.begin(), pattVector.end());
139            unsigned i = 0;
140            while(i < pattVector.size()){
141                std::vector<std::string> pattGroup;
142                std::string prefix = pattVector[i].substr(0, prefixLen);
143                while(i < pattVector.size() && pattVector[i].substr(0, prefixLen) == prefix){
144                    pattGroup.push_back(pattVector[i]);
145                    i++;
146                }
147                pattGroups.push_back(pattGroup);
148            }
149            pattFile.close();
150        }
151        codegen::GroupNum = pattVector.size()/groupSize;
152    }
153
154    // if there are no regexes specified through -e or -f, the first positional argument
155    // must be a regex, not an input file.
156
157    if (pattVector.size() == 0 && inputFiles.size() > 1) {
158        pattVector.push_back(inputFiles[0]);
159        inputFiles.erase(inputFiles.begin());
160    }
161}
162
163typedef void (*preprocessFunctionType)(char * output_data, size_t output_size, const uint32_t fd);
164
165static char * chStream;
166static size_t size;
167
168//class PreprocessPipeline : public PipelineKernel {
169//public:
170//    PreprocessPipeline(EngineInstance & driver, StreamSet * CCResults)
171//     : PipelineKernel(driver,
172//    {},
173//    {Binding{"CCResults", CCResults}},
174//    {Binding{driver.getBuilder()->getInt32Ty(), "fileDescriptor"}},
175//    {}) {
176
177//    }
178//};
179
180class PreprocessKernel final: public pablo::PabloKernel {
181public:
182    PreprocessKernel(const std::unique_ptr<KernelBuilder> & b, StreamSet * BasisBits, StreamSet * CCResults);
183    bool isCachable() const override { return true; }
184    bool hasSignature() const override { return false; }
185protected:
186    void generatePabloMethod() override;
187};
188
189PreprocessKernel::PreprocessKernel(const std::unique_ptr<KernelBuilder> & b, StreamSet * BasisBits, StreamSet * CCResults)
190: PabloKernel(b, "editd_preprocess", {{"basis", BasisBits}}, {{"pat", CCResults}}) {
191
192}
193
194void PreprocessKernel::generatePabloMethod() {
195    PabloBuilder pb(getEntryScope());
196    cc::Parabix_CC_Compiler ccc(getEntryScope(), getInputStreamSet("basis"));
197    PabloAST * A = ccc.compileCC(re::makeCC(re::makeCC(0x41), re::makeCC(0x61)));
198    PabloAST * C = ccc.compileCC(re::makeCC(re::makeCC(0x43), re::makeCC(0x63)));
199    PabloAST * T = ccc.compileCC(re::makeCC(re::makeCC(0x54), re::makeCC(0x74)));
200    PabloAST * G = ccc.compileCC(re::makeCC(re::makeCC(0x47), re::makeCC(0x67)));
201    Var * const pat = getOutputStreamVar("pat");
202    pb.createAssign(pb.createExtract(pat, 0), A);
203    pb.createAssign(pb.createExtract(pat, 1), C);
204    pb.createAssign(pb.createExtract(pat, 2), T);
205    pb.createAssign(pb.createExtract(pat, 3), G);
206}
207
208preprocessFunctionType preprocessPipeline(CPUDriver & pxDriver) {
209    StreamSet * const CCResults = pxDriver.CreateStreamSet(4);
210    auto & b = pxDriver.getBuilder();
211    Type * const int32Ty = b->getInt32Ty();
212    auto P = pxDriver.makePipelineWithIO({}, {{"CCResults", CCResults}}, {{int32Ty, "fileDescriptor"}});
213    Scalar * const fileDescriptor = P->getInputScalar("fileDescriptor");
214    StreamSet * const ByteStream = P->CreateStreamSet(1, 8);
215    P->CreateKernelCall<MMapSourceKernel>(fileDescriptor, ByteStream);
216    StreamSet * const BasisBits = P->CreateStreamSet(8);
217    P->CreateKernelCall<S2PKernel>(ByteStream, BasisBits);
218    P->CreateKernelCall<PreprocessKernel>(BasisBits, CCResults);
219    return reinterpret_cast<preprocessFunctionType>(P->compile());
220}
221
222size_t file_size(const int fd) {
223    struct stat st;
224    if (LLVM_UNLIKELY(fstat(fd, &st) != 0)) {
225        st.st_size = 0;
226    }
227    return st.st_size;
228}
229
230#define ALIGNMENT (32UL)
231
232inline bool is_power_2(const unsigned n) {
233    return ((n & (n - 1)) == 0) && n;
234}
235
236inline unsigned round_up_to(const unsigned x, const unsigned y) {
237    assert(is_power_2(y));
238    return (x + y - 1) & -y;
239}
240
241char * preprocess(preprocessFunctionType preprocess) {
242    std::string fileName = inputFiles[0];
243    const int fd = open(inputFiles[0].c_str(), O_RDONLY);
244    if (LLVM_UNLIKELY(fd == -1)) {
245        std::cerr << "Error: cannot open " << fileName << " for processing.\n";
246        exit(-1);
247    }
248    size = file_size(fd);
249
250    // Given a 8-bit bytestream of length n, we need space for 4 bitstreams of length n ...
251    AlignedAllocator<char, ALIGNMENT> alloc;
252    const auto n = round_up_to(size, 8 * ALIGNMENT);
253    chStream = alloc.allocate((4 * n) / 8);
254    preprocess(chStream, n, fd);
255    close(fd);
256    return chStream;
257}
258
259
260std::string createName(const std::vector<std::string> & patterns) {
261    std::string name = "";
262    for(unsigned i=0; i<patterns.size(); i++)
263        name += patterns[i];
264    return name + std::to_string(editDistance);
265}
266
267class PatternKernel final: public pablo::PabloKernel {
268public:
269    PatternKernel(const std::unique_ptr<KernelBuilder> & b, const std::vector<std::string> & patterns, StreamSet * pat, StreamSet * E);
270    std::string makeSignature(const std::unique_ptr<KernelBuilder> &) override;
271    bool isCachable() const override { return true;}
272protected:
273    void generatePabloMethod() override;
274private:
275    const std::vector<std::string> & mPatterns;
276};
277
278PatternKernel::PatternKernel(const std::unique_ptr<KernelBuilder> & b, const std::vector<std::string> & patterns, StreamSet * pat, StreamSet * E)
279: PabloKernel(b, getStringHash(createName(patterns)),
280{{"pat", pat}},
281{{"E", E}})
282, mPatterns(patterns) {
283
284}
285
286std::string PatternKernel::makeSignature(const std::unique_ptr<KernelBuilder> &) {
287    return getName();
288}
289
290void PatternKernel::generatePabloMethod() {
291    PabloBuilder entry(getEntryScope());
292    Var * const pat = getInputStreamVar("pat");
293    PabloAST * basisBits[4];
294    basisBits[0] = entry.createExtract(pat, 0, "A");
295    basisBits[1] = entry.createExtract(pat, 1, "C");
296    basisBits[2] = entry.createExtract(pat, 2, "T");
297    basisBits[3] = entry.createExtract(pat, 3, "G");
298    re::Pattern_Compiler pattern_compiler(*this);
299    if (optPosition == 0) optPosition = editDistance + 6;
300    pattern_compiler.compile(mPatterns, entry, basisBits, editDistance, optPosition, stepSize);
301}
302
303std::mutex store_mutex;
304extern "C" void wrapped_report_pos(size_t match_pos, int dist) {
305    struct matchPosition curMatch;
306    curMatch.pos = match_pos;
307    curMatch.dist = dist;
308
309    store_mutex.lock();
310    matchList.push_back(curMatch);
311    if(ShowPositions)
312        std::cout << "pos: " << match_pos << ", dist:" << dist << "\n";
313    store_mutex.unlock();
314}
315
316typedef void (*editdFunctionType)(char * byte_data, size_t filesize);
317
318editdFunctionType editdPipeline(CPUDriver & pxDriver, const std::vector<std::string> & patterns) {
319    auto & b = pxDriver.getBuilder();
320    Type * const sizeTy = b->getSizeTy();
321    Type * const inputType = b->getIntNTy(1)->getPointerTo();
322    auto P = pxDriver.makePipeline({Binding{inputType, "input"}, Binding{sizeTy, "fileSize"}});
323    Scalar * const inputStream = P->getInputScalar("input");
324    Scalar * const fileSize = P->getInputScalar("fileSize");
325    b->LinkFunction("wrapped_report_pos", wrapped_report_pos);
326    StreamSet * const ChStream = P->CreateStreamSet(4);
327    P->CreateKernelCall<MemorySourceKernel>(inputStream, fileSize, ChStream);
328    StreamSet * const MatchResults = P->CreateStreamSet(editDistance + 1);
329    P->CreateKernelCall<PatternKernel>(patterns, ChStream, MatchResults);
330    P->CreateKernelCall<editdScanKernel>(MatchResults);
331    return reinterpret_cast<editdFunctionType>(P->compile());
332}
333
334typedef void (*multiEditdFunctionType)(const int fd);
335
336multiEditdFunctionType multiEditdPipeline(CPUDriver & pxDriver) {
337
338    auto & b = pxDriver.getBuilder();
339    auto P = pxDriver.makePipeline({Binding{b->getInt32Ty(), "fileDescriptor"}});
340    b->LinkFunction("wrapped_report_pos", wrapped_report_pos);
341    Scalar * const fileDescriptor = P->getInputScalar("fileDescriptor");
342
343    StreamSet * const ByteStream = P->CreateStreamSet(1, 8);
344    P->CreateKernelCall<MMapSourceKernel>(fileDescriptor, ByteStream);
345
346    std::vector<re::CC *> ccs;
347    ccs.emplace_back(re::makeCC(re::makeCC(0x41), re::makeCC(0x61)));
348    ccs.emplace_back(re::makeCC(re::makeCC(0x43), re::makeCC(0x63)));
349    ccs.emplace_back(re::makeCC(re::makeCC(0x47), re::makeCC(0x67)));
350    ccs.emplace_back(re::makeCC(re::makeCC(0x54), re::makeCC(0x74)));
351
352    StreamSet * const ChStream = P->CreateStreamSet(4);
353    P->CreateKernelCall<DirectCharacterClassKernelBuilder>("editd_cc", ccs, ByteStream, ChStream);
354
355    const auto n = pattGroups.size();
356    std::vector<StreamSet *> MatchResults(n);
357    for(unsigned i = 0; i < n; ++i){
358        MatchResults[i] = P->CreateStreamSet(editDistance + 1);
359        P->CreateKernelCall<PatternKernel>(pattGroups[i], ChStream, MatchResults[i]);
360    }
361
362    StreamSet * MergedResults = MatchResults[0];
363    if (n > 1) {
364        StreamSet * const MergedResults = P->CreateStreamSet();
365        P->CreateKernelCall<StreamsMerge>(MatchResults, MergedResults);
366    }
367    P->CreateKernelCall<editdScanKernel>(MergedResults);
368
369    return reinterpret_cast<multiEditdFunctionType>(P->compile());
370}
371
372typedef void (*editdIndexFunctionType)(char * byte_data, size_t filesize, const char * pattern);
373
374editdIndexFunctionType editdIndexPatternPipeline(CPUDriver & pxDriver, unsigned patternLen) {
375
376    auto & b = pxDriver.getBuilder();
377
378    Type * const inputType = b->getIntNTy(1)->getPointerTo();
379    Type * const sizeTy = b->getSizeTy();
380    Type * const patternPtrTy = PointerType::get(b->getInt8Ty(), 0);
381
382    auto P = pxDriver.makePipeline({Binding{inputType, "input"}, Binding{sizeTy, "fileSize"}, Binding{patternPtrTy, "pattStream"}});
383    Scalar * const inputStream = P->getInputScalar("input");
384    Scalar * const fileSize = P->getInputScalar("fileSize");
385    Scalar * const pattStream = P->getInputScalar("pattStream");
386
387    b->LinkFunction("wrapped_report_pos", wrapped_report_pos);
388
389    StreamSet * const ChStream = P->CreateStreamSet(4);
390    P->CreateKernelCall<MemorySourceKernel>(inputStream, fileSize, ChStream);
391
392    StreamSet * const MatchResults = P->CreateStreamSet(editDistance + 1);
393
394    P->CreateKernelCall<editdCPUKernel>(patternLen, groupSize, pattStream, ChStream, MatchResults);
395
396    P->CreateKernelCall<editdScanKernel>(MatchResults);
397
398    return reinterpret_cast<editdIndexFunctionType>(P->compile());
399}
400
401std::mutex count_mutex;
402size_t groupCount;
403void * DoEditd(void *)
404{
405    size_t groupIdx;
406    count_mutex.lock();
407    groupIdx = groupCount;
408    groupCount++;
409    count_mutex.unlock();
410
411    while (groupIdx < pattGroups.size()){
412
413        CPUDriver pxDriver("editd");
414        auto editd = editdPipeline(pxDriver, pattGroups[groupIdx]);
415        editd(chStream, size);
416
417        count_mutex.lock();
418        groupIdx = groupCount;
419        groupCount++;
420        count_mutex.unlock();
421    }
422
423    pthread_exit(NULL);
424}
425
426int main(int argc, char *argv[]) {
427    codegen::ParseCommandLineOptions(argc, argv);
428    int pattern_segs = 0;
429    int total_len = 0;
430
431    get_editd_pattern(pattern_segs, total_len);
432
433    if (MultiEditdKernels) {
434        CPUDriver pxDriver("editd");
435        auto editd = multiEditdPipeline(pxDriver);
436
437        std::string fileName = inputFiles[0];
438        const int fd = open(inputFiles[0].c_str(), O_RDONLY);
439        if (LLVM_UNLIKELY(fd == -1)) {
440            std::cerr << "Error: cannot open " << fileName << " for processing. Skipped.\n";
441            exit(-1);
442        }
443        editd(fd);
444        close(fd);
445        run_second_filter(pattern_segs, total_len, 0.15);
446        return 0;
447    }
448
449    CPUDriver pxDriver("preprocess");
450    auto preprocess_ptr = preprocessPipeline(pxDriver);
451    preprocess(preprocess_ptr);
452
453    if(pattVector.size() == 1){
454
455        CPUDriver pxDriver("editd");
456        auto editd = editdPipeline(pxDriver, pattVector);
457        editd(chStream, size);
458        std::cout << "total matches is " << matchList.size() << std::endl;
459    }
460    else{
461        if (Threads == 1) {
462            if (EditdIndexPatternKernels) {
463                CPUDriver pxDriver("editd");
464                auto editd_ptr = editdIndexPatternPipeline(pxDriver, pattVector[0].length());
465
466                for(unsigned i=0; i<pattVector.size(); i+=groupSize){
467                    std::string pattern = "";
468                    for (int j=0; j<groupSize; j++){
469                        pattern += pattVector[i+j];
470                    }
471                    editd_ptr(chStream, size, pattern.c_str());
472                }
473            }
474            else {
475                for(unsigned i=0; i<pattGroups.size(); i++){
476
477                    CPUDriver pxDriver("editd");
478                    auto editd = editdPipeline(pxDriver, pattGroups[i]);
479                    editd(chStream, size);
480                }
481            }
482        }
483        else{
484            const unsigned numOfThreads = Threads;
485            pthread_t threads[numOfThreads];
486            groupCount = 0;
487
488            for(unsigned long i = 0; i < numOfThreads; ++i){
489                const int rc = pthread_create(&threads[i], NULL, DoEditd, (void *)i);
490                if (rc) {
491                    llvm::report_fatal_error("Failed to create thread: code " + std::to_string(rc));
492                }
493            }
494
495            for(unsigned i = 0; i < numOfThreads; ++i) {
496                void * status = nullptr;
497                const int rc = pthread_join(threads[i], &status);
498                if (rc) {
499                    llvm::report_fatal_error("Failed to join thread: code " + std::to_string(rc));
500                }
501            }
502
503        }
504        run_second_filter(pattern_segs, total_len, 0.15);
505    }
506
507    AlignedAllocator<char, 32> alloc;
508    alloc.deallocate(chStream, 0);
509
510    return 0;
511}
Note: See TracBrowser for help on using the repository browser.