1 /*
2 * Copyright (C) 2017 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "LSHProjection.h"
18
19 #include "CpuExecutor.h"
20 #include "HalInterfaces.h"
21 #include "util/hash/farmhash.h"
22
23 namespace android {
24 namespace nn {
25
LSHProjection(const Operation & operation,std::vector<RunTimeOperandInfo> & operands)26 LSHProjection::LSHProjection(const Operation& operation,
27 std::vector<RunTimeOperandInfo>& operands) {
28 input_ = GetInput(operation, operands, kInputTensor);
29 weight_ = GetInput(operation, operands, kWeightTensor);
30 hash_ = GetInput(operation, operands, kHashTensor);
31
32 type_ = static_cast<LSHProjectionType>(
33 getScalarData<int32_t>(*GetInput(operation, operands, kTypeParam)));
34
35 output_ = GetOutput(operation, operands, kOutputTensor);
36 }
37
Prepare(const Operation & operation,std::vector<RunTimeOperandInfo> & operands,Shape * outputShape)38 bool LSHProjection::Prepare(const Operation &operation,
39 std::vector<RunTimeOperandInfo>& operands,
40 Shape *outputShape) {
41 const int num_inputs = NumInputsWithValues(operation, operands);
42 NN_CHECK(num_inputs == 3 || num_inputs == 4);
43 NN_CHECK_EQ(NumOutputs(operation), 1);
44
45 const RunTimeOperandInfo *hash = GetInput(operation, operands, kHashTensor);
46 NN_CHECK_EQ(NumDimensions(hash), 2);
47 // Support up to 32 bits.
48 NN_CHECK(SizeOfDimension(hash, 1) <= 32);
49
50 const RunTimeOperandInfo* input = GetInput(operation, operands, kInputTensor);
51 NN_CHECK(NumDimensions(input) >= 1);
52
53 auto type = static_cast<LSHProjectionType>(
54 getScalarData<int32_t>(operands[operation.inputs[kTypeParam]]));
55 switch (type) {
56 case LSHProjectionType_SPARSE:
57 NN_CHECK(NumInputsWithValues(operation, operands) == 3);
58 outputShape->dimensions = { SizeOfDimension(hash, 0) };
59 break;
60 case LSHProjectionType_DENSE: {
61 RunTimeOperandInfo *weight = GetInput(operation, operands, kWeightTensor);
62 NN_CHECK_EQ(NumInputsWithValues(operation, operands), 4);
63 NN_CHECK_EQ(NumDimensions(weight), 1);
64 NN_CHECK_EQ(SizeOfDimension(weight, 0), SizeOfDimension(input, 0));
65 outputShape->dimensions = { SizeOfDimension(hash, 0) * SizeOfDimension(hash, 1) };
66 break;
67 }
68 default:
69 return false;
70 }
71
72 outputShape->type = OperandType::TENSOR_INT32;
73 outputShape->offset = 0;
74 outputShape->scale = 0.f;
75
76 return true;
77 }
78
79 // Compute sign bit of dot product of hash(seed, input) and weight.
80 // NOTE: use float as seed, and convert it to double as a temporary solution
81 // to match the trained model. This is going to be changed once the new
82 // model is trained in an optimized method.
83 //
running_sign_bit(const RunTimeOperandInfo * input,const RunTimeOperandInfo * weight,float seed)84 int running_sign_bit(const RunTimeOperandInfo* input,
85 const RunTimeOperandInfo* weight, float seed) {
86 double score = 0.0;
87 int input_item_bytes = sizeOfData(input->type, input->dimensions) /
88 SizeOfDimension(input, 0);
89 char* input_ptr = (char*)(input->buffer);
90
91 const size_t seed_size = sizeof(float);
92 const size_t key_bytes = sizeof(float) + input_item_bytes;
93 std::unique_ptr<char[]> key(new char[key_bytes]);
94
95 for (uint32_t i = 0; i < SizeOfDimension(input, 0); ++i) {
96 // Create running hash id and value for current dimension.
97 memcpy(key.get(), &seed, seed_size);
98 memcpy(key.get() + seed_size, input_ptr, input_item_bytes);
99
100 int64_t hash_signature = farmhash::Fingerprint64(key.get(), key_bytes);
101 double running_value = static_cast<double>(hash_signature);
102 input_ptr += input_item_bytes;
103 if (weight->lifetime == OperandLifeTime::NO_VALUE) {
104 score += running_value;
105 } else {
106 score += reinterpret_cast<float*>(weight->buffer)[i] * running_value;
107 }
108 }
109
110 return (score > 0) ? 1 : 0;
111 }
112
SparseLshProjection(const RunTimeOperandInfo * hash,const RunTimeOperandInfo * input,const RunTimeOperandInfo * weight,int32_t * out_buf)113 void SparseLshProjection(const RunTimeOperandInfo* hash,
114 const RunTimeOperandInfo* input,
115 const RunTimeOperandInfo* weight, int32_t* out_buf) {
116 int num_hash = SizeOfDimension(hash, 0);
117 int num_bits = SizeOfDimension(hash, 1);
118 for (int i = 0; i < num_hash; i++) {
119 int32_t hash_signature = 0;
120 for (int j = 0; j < num_bits; j++) {
121 float seed = reinterpret_cast<float*>(hash->buffer)[i * num_bits + j];
122 int bit = running_sign_bit(input, weight, seed);
123 hash_signature = (hash_signature << 1) | bit;
124 }
125 *out_buf++ = hash_signature;
126 }
127 }
128
DenseLshProjection(const RunTimeOperandInfo * hash,const RunTimeOperandInfo * input,const RunTimeOperandInfo * weight,int32_t * out_buf)129 void DenseLshProjection(const RunTimeOperandInfo* hash,
130 const RunTimeOperandInfo* input,
131 const RunTimeOperandInfo* weight, int32_t* out_buf) {
132 int num_hash = SizeOfDimension(hash, 0);
133 int num_bits = SizeOfDimension(hash, 1);
134 for (int i = 0; i < num_hash; i++) {
135 for (int j = 0; j < num_bits; j++) {
136 float seed = reinterpret_cast<float*>(hash->buffer)[i * num_bits + j];
137 int bit = running_sign_bit(input, weight, seed);
138 *out_buf++ = bit;
139 }
140 }
141 }
142
Eval()143 bool LSHProjection::Eval() {
144 int32_t* out_buf = reinterpret_cast<int32_t*>(output_->buffer);
145
146 switch (type_) {
147 case LSHProjectionType_DENSE:
148 DenseLshProjection(hash_, input_, weight_, out_buf);
149 break;
150 case LSHProjectionType_SPARSE:
151 SparseLshProjection(hash_, input_, weight_, out_buf);
152 break;
153 default:
154 return false;
155 }
156 return true;
157 }
158
159 } // namespace nn
160 } // namespace android
161