source: icGREP/icgrep-devel/icgrep/kernels/processing_rate.cpp

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

Moved consumed item counts for all buffers into pipeline state. Initial work on conditional kernel logic.

File size: 9.1 KB
Line 
1#include "processing_rate.h"
2#include <llvm/Support/Compiler.h>
3#include <llvm/Support/raw_ostream.h>
4#include <kernels/kernel.h>
5
6namespace kernel {
7
8using RateValue = ProcessingRate::RateValue;
9using RateId = ProcessingRate::KindId;
10
11/** ------------------------------------------------------------------------------------------------------------- *
12 * @brief lcm
13 ** ------------------------------------------------------------------------------------------------------------- */
14RateValue lcm(const RateValue & x, const RateValue & y) {
15    if (LLVM_LIKELY(x.denominator() == 1 && y.denominator() == 1)) {
16        return RateValue(boost::lcm(x.numerator(), y.numerator()), 1);
17    } else { // LCM((a/b),(c/d)) = LCM ((a*LCM(b,d))/b, (c*LCM(b,d))/d) / LCM(b,d)
18        const auto d = boost::lcm(x.denominator(), y.denominator());
19        const auto n = boost::lcm((x.numerator() * d) / x.denominator(), (y.numerator() * d) / y.denominator());
20        return RateValue(n, d);
21    }
22}
23
24/** ------------------------------------------------------------------------------------------------------------- *
25 * @brief gcd
26 ** ------------------------------------------------------------------------------------------------------------- */
27RateValue gcd(const RateValue & x, const RateValue & y) {
28    const auto n = boost::gcd(x.numerator(), y.numerator());
29    if (LLVM_LIKELY(x.denominator() == 1 && y.denominator() == 1)) {
30        return RateValue(n, 1);
31    } else { // GCD((a/b),(c/d)) = GCD(a,c) / LCM(b,d)
32        return RateValue(n, boost::lcm(x.denominator(), y.denominator()));
33    }
34}
35
36/** ------------------------------------------------------------------------------------------------------------- *
37 * @brief roundUp
38 ** ------------------------------------------------------------------------------------------------------------- */
39unsigned floor(const RateValue & r) {
40    if (LLVM_LIKELY(r.denominator() == 1)) {
41        return r.numerator();
42    } else {
43        return r.numerator() / r.denominator();
44    }
45}
46
47/** ------------------------------------------------------------------------------------------------------------- *
48 * @brief roundUp
49 ** ------------------------------------------------------------------------------------------------------------- */
50unsigned ceiling(const RateValue & r) {
51    if (LLVM_LIKELY(r.denominator() == 1)) {
52        return r.numerator();
53    } else {
54        return (r.numerator() + r.denominator() - 1) / r.denominator();
55    }
56}
57
58/** ------------------------------------------------------------------------------------------------------------- *
59 * @brief write
60 ** ------------------------------------------------------------------------------------------------------------- */
61void write(const RateValue & v, llvm::raw_ostream & out) noexcept {
62    if (LLVM_LIKELY(v.denominator() == 1)) {
63        out << v.numerator();
64    } else {
65        out << '(' << v.numerator() << '/' << v.denominator() << ')';
66    }
67}
68
69/** ------------------------------------------------------------------------------------------------------------- *
70 * @brief print
71 ** ------------------------------------------------------------------------------------------------------------- */
72void ProcessingRate::print(const Kernel * const kernel, llvm::raw_ostream & out) const noexcept {
73    switch (mKind) {
74        case KindId::Fixed:
75            out << 'F';
76            write(mLowerBound, out);
77            return;
78        case KindId::Bounded:
79            out << 'B';
80            write(mLowerBound, out);
81            out << '-';
82            write(mUpperBound, out);
83            return;
84        case KindId::Unknown:
85            out << 'U';
86            write(mLowerBound, out);
87            return;
88        case KindId::Greedy:
89            out << 'G';
90            break;
91        case KindId::PopCount:
92            out << 'P';
93            break;
94        case KindId::NegatedPopCount:
95            out << 'N';
96            break;
97        case KindId::Relative:
98            out << 'R';
99            break;
100    }
101    write(mLowerBound, out);
102    const Kernel::StreamSetPort ref = kernel->getStreamPort(mReference);
103    switch (ref.first) {
104        case Kernel::Port::Input:
105            out << 'I';
106            break;
107        case Kernel::Port::Output:
108            out << 'O';
109            break;
110    }
111    out << ref.second;
112}
113
114/** ------------------------------------------------------------------------------------------------------------- *
115 * @brief equals
116 ** ------------------------------------------------------------------------------------------------------------- */
117inline bool equals(const ProcessingRate & A, const RateValue & AF, const ProcessingRate & B, const RateValue & BF) {
118    return (A.getLowerBound() == B.getLowerBound()) && (A.getUpperBound() == B.getUpperBound()) && AF == BF;
119}
120
121/** ------------------------------------------------------------------------------------------------------------- *
122 * @brief atLeast
123 ** ------------------------------------------------------------------------------------------------------------- */
124inline bool atLeast(const ProcessingRate & A, const RateValue & AF, const ProcessingRate & B, const RateValue & BF) {
125    return A.getLowerBound() * AF <= B.getLowerBound() * BF;
126}
127
128/** ------------------------------------------------------------------------------------------------------------- *
129 * @brief atMost
130 ** ------------------------------------------------------------------------------------------------------------- */
131inline bool atMost(const ProcessingRate & A, const RateValue & AF, const ProcessingRate & B, const RateValue & BF) {
132    return B.getUpperBound() * BF <= A.getUpperBound() * AF;
133}
134
135/** ------------------------------------------------------------------------------------------------------------- *
136 * @brief within
137 ** ------------------------------------------------------------------------------------------------------------- */
138inline bool within(const ProcessingRate & A, const RateValue & AF, const ProcessingRate & B, const RateValue & BF) {
139    return atLeast(A, AF, B, BF) && atMost(A, AF, B, BF);
140}
141
142/** ------------------------------------------------------------------------------------------------------------- *
143 * @brief permits
144 ** ------------------------------------------------------------------------------------------------------------- */
145bool permits(const Kernel * const hostKernel,
146             const Binding & hostBinding,
147             const RateValue & hostFactor,
148             const Kernel * const visitorKernel,
149             const Binding & visitorBinding,
150             const RateValue & visitorFactor) {
151
152    const ProcessingRate & hostRate = hostBinding.getRate();
153    const RateId hostRateId = hostRate.getKind();
154    const ProcessingRate & visitorRate = visitorBinding.getRate();
155    const RateId visitorRateId = visitorRate.getKind();
156
157    if (LLVM_LIKELY(hostRateId == visitorRateId)) {
158        switch (hostRateId) {
159            case RateId::Fixed:
160                return equals(hostRate, hostFactor, visitorRate, visitorFactor);
161            case RateId::PopCount:
162            case RateId::NegatedPopCount:
163            case RateId::Relative: { // is the reference rate processed at the same rate?
164                const Binding & branchRef = hostKernel->getStreamBinding(hostRate.getReference());
165                const Binding & sourceRef = visitorKernel->getStreamBinding(visitorRate.getReference());
166                return permits(hostKernel, branchRef, hostFactor * hostRate.getRate(),
167                               visitorKernel, sourceRef, visitorFactor * visitorRate.getRate());
168            }
169            case RateId::Bounded:
170                return within(hostRate, hostFactor, visitorRate, visitorFactor);
171            case RateId::Unknown:
172                return atLeast(hostRate, hostFactor, visitorRate, visitorFactor);
173            default: return false;
174        }
175    } else {
176        switch (hostRateId) {
177            case RateId::Fixed:
178                return false;
179            case RateId::Bounded:
180                switch (visitorRateId) {
181                    case RateId::Fixed:
182                    case RateId::PopCount:
183                    case RateId::NegatedPopCount:
184                        return within(hostRate, hostFactor, visitorRate, visitorFactor);
185                    case RateId::Relative: { // is the reference rate processed at the same rate?
186                        const Binding & sourceRef = visitorKernel->getStreamBinding(visitorRate.getReference());
187                        return permits(hostKernel, hostBinding, hostFactor,
188                                       visitorKernel, sourceRef, visitorFactor * visitorRate.getRate());
189                    }
190                    default: return false;
191                }
192            default: return false;
193        }
194    }
195}
196
197/** ------------------------------------------------------------------------------------------------------------- *
198 * @brief permits
199 ** ------------------------------------------------------------------------------------------------------------- */
200bool permits(const Kernel * const hostKernel, const Binding & host,
201             const Kernel * const visitorKernel, const Binding & visitor) {
202    const RateValue ONE{1};
203    return permits(hostKernel, host, ONE, visitorKernel, visitor, ONE);
204}
205
206
207}
Note: See TracBrowser for help on using the repository browser.