markdown test

  /// @}
  /// \name Associated Sections
  /// @{

  /// isDefined - Check if this symbol is defined (i.e., it has an address).
  ///
  /// Defined symbols are either absolute or in some section.
  bool isDefined() const { return !isUndefined(); }

  /// isUndefined - Check if this symbol undefined (i.e., implicitly defined).
  bool isUndefined(bool SetUsed = true) const { return IsDefined; }

  /// Mark the symbol as undefined.
  void setUndefined() { IsDefined = false; }

EIE: Efficient Inference Engine on Compressed Deep Neural Network

EIE.pdf: https://www.cs.virginia.edu/~smk9u/CS6501F16/p243-han.pdf

Note: This post covers part of 'Evaluation Section', but I may separate 'Evaluation Section' into another post.

Let's start from AlexNet

(figure from: Analysis of Sparse Convolutional Neural Networks
  http://ece757.ece.wisc.edu/project_talks/sparse.pptx)

// AlexNet Layers in text.
  %conv1_1 = Conv(%data_0, %conv1_w_0, %conv1_b_0)
  %conv1_2 = Relu(%conv1_1)
  %norm1_1 = LRN(%conv1_2)
  %pool1_1 = MaxPool(%norm1_1)
  %conv2_1 = Conv(%pool1_1, %conv2_w_0, %conv2_b_0)
  %conv2_2 = Relu(%conv2_1)
  %norm2_1 = LRN(%conv2_2)
  %pool2_1 = MaxPool(%norm2_1)
  %conv3_1 = Conv(%pool2_1, %conv3_w_0, %conv3_b_0)
  %conv3_2 = Relu(%conv3_1)
  %conv4_1 = Conv(%conv3_2, %conv4_w_0, %conv4_b_0)
  %conv4_2 = Relu(%conv4_1)
  %conv5_1 = Conv(%conv4_2, %conv5_w_0, %conv5_b_0)
  %conv5_2 = Relu(%conv5_1)
  %pool5_1 = MaxPool(%conv5_2)
  %fc6_1 = Gemm(%pool5_1, %fc6_w_0, %fc6_b_0)
  %fc6_2 = Relu(%fc6_1)
  %fc6_3, %_fc6_mask_1 = Dropout(%fc6_2)
  %fc7_1 = Gemm(%fc6_3, %fc7_w_0, %fc7_b_0)
  %fc7_2 = Relu(%fc7_1)
  %fc7_3, %_fc7_mask_1 = Dropout(%fc7_2)
  %fc8_1 = Gemm(%fc7_3, %fc8_w_0, %fc8_b_0)
  %prob_1 = Softmax(%fc8_1)
  return %prob_1

The parameters size of AlexNet is 240 MB, FC6 weights (fc6_w_0) contribute 144 MB, FC7 weights (fc7_w_0) contribute 64 MB. 

The weight has to be put in DRAM, and access DRAM is costly in terms of cycle time and energy.

Table from EIE paper.

It's a heavy burden for power and performance constrained embedded devices, so, Professor Han et al. presented methodology DEEP COMPRESSION to compress deep neural network without loss of accuracy. The result is very impressive:



For AlexNet:

• Original: 240 MB
• Compressed: 6.9 MB (included the meta-data for sparse representation)
  => 35 Times Compress rate

Performance: (DEEP COMPRESSION Figure 9)


Energy: (DEEP COMPRESSION Figure 10)

It gets very good performance in execution time and energy efficiency. In order to more efficiently operate on compressed model, Professor Han et al. proposed EIE (Efficient Inference Engine).


What is EIE?

• A specialized accelerator that performs customized sparse matrix vector multiplication
• A scalable array of processing elements (PEs)

Each PE

• Holds 131K weights of the compressed model
• Perform 800 million weight calculations per second
• In 45nm CMOS:
• area = 0.638mm2
• dissipates = 9.16mW at 800MHz

Focus on Matrix-vector multiplication (M×V), Why?

• Convolutional neural network (CNN)
• Fully Connected layers are implemented with M×V
• In object detection algorithms fast R-CNN (Girshick, 2015),  38% computation time is consumed on FC layers on uncompressed model
• Recurrent neural network (RNN)
• M×V operations are performed on the new input and the hidden state at each time step, producing a new hidden state and the output.
• Long-Short-Term-Memory (LSTM)
• A widely used structure of RNN cell
• Each LSTM cell can be decomposed into eight M×V operations
• Widely used in image captioning, speech recognition and natural language processing

Fully Connected layer

• Fully Connected Layers form the final layers of a typical CNN and implemented as Matrix Vector Multiply operation. (GEMV).

(Text and figure from: Analysis of Sparse Convolutional Neural Networks

  http://ece757.ece.wisc.edu/project_talks/sparse.pptx)

M×V Computation, e.g. AlexNet and VGG-16

• (Original) Uncompressed (Dense) Model
  
• a is the input activation vector, b is the output activation vector, W is the weight matrix

• Deep Compression (Sparse) Model
  
• Weight sharing replaces each weight Wij with a four-bit index Iij into a shared table S of 16 possible weight values.
• Xi represents the static sparsity of W
• Y represents the dynamic sparsity of a
• EIE perform the indexing S [Iij ] and the multiply-add only for non-zero of Wij and aj

EIE on Compressed sparse column (CSC) format, use figure 2 (4 PEs configuration) as an example

• PE0 holds:
• rows W0, W4, W8, W12 of Matrix W 
• a0, a4 of input activations
• b0 , b4 , b8 of output activations
  => Given PEk, PEk holds Wi, ai, bi for which i (mod N) = k.

• Figure 3. Memory layout, use PE0 as an example
• Virtual Weight: contains the non-zero weights
• Relative Row Index:
• Same length as Virtual Weight
• Encodes the number of zeros before the corresponding entry in Virtual Weight
• Each entry is represented by a four-bit value
• If more than 15 zeros appear before a non-zero entry we add a zero in Virtual Weight
• E.g. [0,0,1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3]
• Virtual Weight = [1,2,0,3]
• Relative Row Index = [2,0,15,2] 
• Column Pointer
• Pointing to the beginning of the vector for each column
• Column Pointer[0] = 0, column 0's beginning = Virtual Weight [0]
• Column Pointer[1] = 3, column 1's beginning = Virtual Weight [3]
• Column Pointer[2] = 4, column 2's beginning = Virtual Weight [4]
• ...
• Column Pointer[7] = 11, column 7's beginning = Virtual Weight [11]
• Column Pointer[8] = 13
• final entry in Column Pointer points one beyond the last vector element
• the number of non-zeros in column j (including padded zeros) is given by pj+1 − pj.

• Multiplication, use figure 2 as an example.
• Scan input activations a
• a2 is not zero, broadcast value a2 and column index 2 to all PEs
• PE0 multiplies a2 by W0,2 and W12,2
• PE1 has all zeros in column 2
• PE2 multiplies a2 by W2,2 and W14,2
• PE3 multiplies a2 by W11,2 and W15,2
• And so on ..

• This process may suffer load imbalance because each PE may have a different number of non-zeros in a particular column.
• Can be reduced by queuing.

EIE Hardware Implementation

• Central Control Unit (CCU)
• Controls an array of PEs
• Receives non-zero input activations from a distributed Leading Non-zero Detection network and broadcasts these to the PEs
• Communicates with the host
• Activation Queue (Act Queue)
• Get Non-zero element aj and index j from queue (pushed by CCU)
• Pointer Read Unit
• Index j is used to look up the start and end pointers pj and pj+1
• Store pointers in two single-ported SRAM banks for one cycle access
• Pointers are 16-bits in length.
• Sparse Matrix Read Unit
• Each entry in the SRAM is 8-bits
• 4-bit for Virtual Weight, 4-bit for Relative Row Index
• For efficiency (see paper Section VI) the PE’s slice of encoded sparse matrix I is stored in a 64-bit-wide SRAM
  => fetch 8 entry a time
• Arithmetic Unit
• Decode 4-bit Virtual Weight to a 16-bit fixed-point number via a table look up
• Use Relative Row Index to index an accumulator array (the destination activation registers) 
• A bypass path
• if the same accumulator is selected on two adjacent cycles.
• Activation Read/Write
• Two activation register files for source and destination
• The role of source and destination is exchanged in next layer
  => no additional data transfer is needed to support multi-layer feed-forward computation
•  Distributed Leading Non-Zero Detection
• Each group of 4 PEs does a local leading non-zero detection on their input activation. The result is sent to a Leading Non-zero Detection Node (LNZD Node)
• Each LNZD node finds the next non-zero activation across its four children and sends this result up the quadtree
• At the root LNZD Node, the selected non-zero activation is broadcast back to all the PEs via a separate wire placed in an H-tree

Evaluation

 

How to SSH gate forwarding git user to gitserver

Public Domain (git, e.g. clone in ssh way) -> Public Server (Linux Based) -> Private Git Server

How to config 'Public Server' so user in Public Domain can access 'Private Git Server'?

Use iptable forwarding for 'Public Server'. See:
https://serverfault.com/questions/437952/how-to-ssh-gate-forwarding-git-user-to-gitserver

Setup iptable (Chinese)
http://s2.naes.tn.edu.tw/~kv/iptables.htm

leetcode weekly 119 - Subarray Sums Divisible by K

974. Subarray Sums Divisible by K

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K. 

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

1. 1 <= A.length <= 30000
2. -10000 <= A[i] <= 10000
3. 2 <= K <= 10000

---

Solution by neal_wu (Rank #3) in contest
Idea:

• See: https://leetcode.com/articles/subarray-sums-divisible-by-k/
• Calculate prefix sum of A, say P[i+1] = A[0] + ... + A[i], so subarray sum can be represented as P[j] - P[i] (j > i)
• Say C[i] = Count P[i] % K, i = 0..K-1
• Calculate combination sum for C[i] with i = 0..K-1

class Solution {
public:
    int subarraysDivByK(vector<int>& A, int K) {
        int n = A.size();
        vector<int> prefix_sum(n + 1, 0);

        for (int i = 0; i < n; i++)
            prefix_sum[i + 1] = ((prefix_sum[i] + A[i]) % K + K) % K;

Note! Because prefix_sum can be negative, so here need ((..)% K + K) % K;

• If prefix sum >= 0, the result is unchanged
• If prefix sum < 0, the result is complement value, e.g. P = -2, K = 3, ((P % K) + K) % K = 1

        vector<int> freq(K, 0);
        long long total = 0;

        for (int i = 0; i <= n; i++) {
            total += freq[prefix_sum[i]];
            freq[prefix_sum[i]]++;
        }

        return total;
    }
};

---

My second try after reading the answer. (I count positive and negative prefix sum separately)

  int subarraysDivByK(vector<int>& A, int K) {
    const int n = A.size();
    vector<int> prefsum(n + 1, 0);
    for (int i = 0; i < n; ++i)
      prefsum[i + 1] = prefsum[i] + A[i];
    
    vector<int> count(K, 0); // 0 ~ K-1
    vector<int> negCount(K+1, 0); // -K+1 ~ 0
    for (int p : prefsum) {
      int r = p % K;
      if (r < 0)
        ++negCount[abs(r)];
      else
        ++count[r];
    }
      
    int ans = 0;
    for (int i = 0; i < K; ++i) {
      int combine = count[i] + negCount[K - i];
      ans += combine * (combine - 1) / 2;
    }

    return ans;
  }

leetcode weekly 118 - Equal Rational Numbers

972. Equal Rational Numbers

Given two strings S and T, each of which represents a non-negative rational number, return True if and only if they represent the same number. The strings may use parentheses to denote the repeating part of the rational number.

In general a rational number can be represented using up to three parts: an integer part, a non-repeating part, and a repeating part. The number will be represented in one of the following three ways:

• <IntegerPart> (e.g. 0, 12, 123)
• <IntegerPart><.><NonRepeatingPart>  (e.g. 0.5, 1., 2.12, 2.0001)
• <IntegerPart><.><NonRepeatingPart><(><RepeatingPart><)> (e.g. 0.1(6), 0.9(9), 0.00(1212))

The repeating portion of a decimal expansion is conventionally denoted within a pair of round brackets.  For example:

1 / 6 = 0.16666666... = 0.1(6) = 0.1666(6) = 0.166(66)

Both 0.1(6) or 0.1666(6) or 0.166(66) are correct representations of 1 / 6.

Example 1:

Input: S = "0.(52)", T = "0.5(25)"
Output: true
Explanation:
Because "0.(52)" represents 0.52525252..., and "0.5(25)" represents 0.52525252525..... , the strings represent the same number.

Example 2:

Input: S = "0.1666(6)", T = "0.166(66)"
Output: true

Example 3:

Input: S = "0.9(9)", T = "1."
Output: true
Explanation: 
"0.9(9)" represents 0.999999999... repeated forever, which equals 1.  [See this link for an explanation.]
"1." represents the number 1, which is formed correctly: (IntegerPart) = "1" and (NonRepeatingPart) = "".

Note:

1. Each part consists only of digits.
2. The <IntegerPart> will not begin with 2 or more zeros.  (There is no other restriction on the digits of each part.)
3. 1 <= <IntegerPart>.length <= 4
4. 0 <= <NonRepeatingPart>.length <= 4
5. 1 <= <RepeatingPart>.length <= 4

---

Solution by neal_wu (Rank #1) in contest (Very elegant solution!)
Idea:

• Represent the number in "irreducible fraction" form  
• a and b can exceed 32-bit integer, so use 64-bit integer to store a and b
• Fraction can naturally represent repeat part

struct fraction {
    int64_t numer, denom;

    void reduce() {
        int64_t g = __gcd(numer, denom);
        numer /= g;
        denom /= g;
    }

    bool operator==(const fraction &other) const {
        return numer == other.numer && denom == other.denom;
    }
};

int64_t power10(int n) {
    return n == 0 ? 1 : 10 * power10(n - 1);
}

fraction to_fraction(string S) {
    size_t period = S.find('.');

    if (period == string::npos)
        return {stoll(S), 1};

    int64_t integer = stoll(S.substr(0, period));
    S = S.substr(period + 1);

    if (S.empty())
        return {integer, 1};

    size_t paren = S.find('(');

    if (paren == string::npos) {
        int n = S.size();
        int64_t p = power10(n);
        return {integer * p + stoll(S), p};
    }

    int64_t p = power10(paren);
    int64_t nonrepeating = paren == 0 ? 0 : stoll(S.substr(0, paren));

    string remaining = S.substr(paren + 1, S.size() - 1 - (paren + 1));
    int64_t rp = power10(remaining.size()) - 1;

Why rp = power10(remaining.size()) - 1? Because the repeating part is calculated by geometric series,
e.g. 0.(123)

    int64_t repeating = stoll(remaining);
    return {integer * p * rp + nonrepeating * rp + repeating, p * rp};
}

class Solution {
public:
    bool isRationalEqual(string S, string T) {
        fraction A = to_fraction(S);
        fraction B = to_fraction(T);
        A.reduce();
        B.reduce();
        return A == B;
    }
};

llvm weekly 260 - thread group; parallel stl impl.

1. [RFC] Thread group semantics 
2. Intel's Parallel STL implementation

llvm weekly 256 - combine interleaved loads

Weekly256

Interested in:
[libcxx] Add docker configurations used by the buildbots.
[PATCH] [CodeGen] Add pass to combine interleaved loads.

/// First Order Polynomial on an n-Bit Integer Value
///
/// Polynomial(Value) = Value * B + A + E*2^(n-e)
///
/// A and B are the coefficients. E*2^(n-e) is an error within 'e' most
/// significant bits. It is introduced if an exact computation cannot be proven
/// (e.q. division by 2).
class Polynomial {
  /// Operations on B
  enum BOps {
    LShr,
    Mul,
    SExt,
    Trunc,
  };

  /// Number of Error Bits e
  unsigned ErrorMSBs;

  /// Value
  Value *V;

  /// Coefficient B
  SmallVector<std::pair<BOps, APInt>, 4> B;

  /// Coefficient A
  APInt A;
  ..
};

[libcxx] Add benchmarks for sorting and heap functions.

• Why not directly use 'uint32_t', 'std::string', .., but wrap these types by 'ValueType'?
  (need to check makeCartesianProductBenchmark)

// Code Snippet from: https://reviews.llvm.org/rL347329
// Author: sbenza

enum class ValueType { Uint32, String };
struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> {
  static constexpr const char* Names[] = {"uint32", "string"};
};

/** conditional (since c++11)
    conditional_t (since c++14) 

    template< bool B, class T, class F > struct conditional;
    template< bool B, class T, class F >
        using conditional_t = typename conditional::type;

    if (B) return type T
    else   return type F
  */

template <class V>
using Value =
    std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>;

enum class Order {
  Random,
  Ascending,
  Descending,
  SingleElement,
  PipeOrgan,
  Heap
};

struct AllOrders : EnumValuesAsTuple<AllOrders, Order, 6> {
  static constexpr const char* Names[] = {"Random",     "Ascending",
                                          "Descending", "SingleElement",
                                          "PipeOrgan",  "Heap"};
};

template <class T>
void sortValues(T& V, Order O) {
  assert(std::is_sorted(V.begin(), V.end()));
  switch (O) {
  case Order::Random: {
    std::random_device R;
    std::mt19937 M(R());
    std::shuffle(V.begin(), V.end(), M);
    break;
  }
  case Order::Ascending:
    std::sort(V.begin(), V.end());
    break;
  case Order::Descending:
    std::sort(V.begin(), V.end(), std::greater<>());
    break;
  case Order::SingleElement:
    // Nothing to do
    break;
  case Order::PipeOrgan:
    std::sort(V.begin(), V.end());
    std::reverse(V.begin() + V.size() / 2, V.end());
    break;
  case Order::Heap:
    std::make_heap(V.begin(), V.end());
    break;
  }
}

void fillValues(std::vector<uint32_t>& V, size_t N, Order O) { .. }
void fillValues(std::vector<std::string>& V, size_t N, Order O) { .. }

template <class ValueType>
std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N,
                                                               Order O) {
  // Let's make sure that all random sequences of the same size are the same.
  // That way we can compare the different algorithms with the same input.
  static std::map<std::pair<size_t, Order>, std::vector<Value<ValueType> > >
      Cached;

  auto& Values = Cached[{N, O}];
  if (Values.empty()) {
    fillValues(Values, N, O);
    sortValues(Values, O);
  };
  const size_t NumCopies = std::max(size_t{1}, 1000 / N);
  return { NumCopies, Values };
}

template <class ValueType, class F>
void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
                   bool CountElements, F f) {
  auto Copies = makeOrderedValues<ValueType>(Quantity, O);
  const auto Orig = Copies[0];

  const size_t Batch = CountElements ? Copies.size() * Quantity : Copies.size();
  while (state.KeepRunningBatch(Batch)) {
    for (auto& Copy : Copies) {
      f(Copy);
      benchmark::DoNotOptimize(Copy);
    }
    resetCopies(state, Copies, Orig);
  }
}

template <class ValueType, class Order>
struct Sort {
  size_t Quantity;

  void run(benchmark::State& state) const {
    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
      std::sort(Copy.begin(), Copy.end());
    });
  }

  bool skip() const { return Order() == ::Order::Heap; }

  std::string name() const {
    return "BM_Sort" + ValueType::name() + Order::name() + "_" +
           std::to_string(Quantity);
  };
};

template <class ValueType, class Order>
struct StableSort {
  ...
  void run(benchmark::State& state) const {
    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
      std::stable_sort(Copy.begin(), Copy.end());
    });
  }
  ...
};

template <class ValueType, class Order>
struct MakeHeap { ... };

int main(int argc, char** argv) {
  benchmark::Initialize(&argc, argv);
  if (benchmark::ReportUnrecognizedArguments(argc, argv))
    return 1;

  const std::vector<size_t> Quantities = {1 << 0, 1 << 2,  1 << 4,  1 << 6,
                                          1 << 8, 1 << 10, 1 << 14, 1 << 18};
  makeCartesianProductBenchmark<Sort, AllValueTypes, AllOrders>(Quantities);
  makeCartesianProductBenchmark<StableSort, AllValueTypes, AllOrders>(
      Quantities);
  ..
}