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 "Tracing.h"
21 #include "Utils.h"
22 
23 #include "utils/hash/farmhash.h"
24 
25 namespace android {
26 namespace nn {
27 
LSHProjection(const Operation & operation,std::vector<RunTimeOperandInfo> & operands)28 LSHProjection::LSHProjection(const Operation& operation,
29                              std::vector<RunTimeOperandInfo>& operands) {
30     input_ = GetInput(operation, operands, kInputTensor);
31     weight_ = GetInput(operation, operands, kWeightTensor);
32     hash_ = GetInput(operation, operands, kHashTensor);
33 
34     type_ = static_cast<LSHProjectionType>(
35             getScalarData<int32_t>(*GetInput(operation, operands, kTypeParam)));
36 
37     output_ = GetOutput(operation, operands, kOutputTensor);
38 }
39 
Prepare(const Operation & operation,std::vector<RunTimeOperandInfo> & operands,Shape * outputShape)40 bool LSHProjection::Prepare(const Operation& operation, std::vector<RunTimeOperandInfo>& operands,
41                             Shape* outputShape) {
42     const int num_inputs = NumInputsWithValues(operation, operands);
43     NN_CHECK(num_inputs == 3 || num_inputs == 4);
44     NN_CHECK_EQ(NumOutputs(operation), 1);
45 
46     const RunTimeOperandInfo* hash = GetInput(operation, operands, kHashTensor);
47     NN_CHECK_EQ(NumDimensions(hash), 2);
48     // Support up to 32 bits.
49     NN_CHECK(SizeOfDimension(hash, 1) <= 32);
50 
51     const RunTimeOperandInfo* input = GetInput(operation, operands, kInputTensor);
52     NN_CHECK(NumDimensions(input) >= 1);
53 
54     auto type = static_cast<LSHProjectionType>(
55             getScalarData<int32_t>(operands[operation.inputs[kTypeParam]]));
56     switch (type) {
57         case LSHProjectionType_SPARSE:
58         case LSHProjectionType_SPARSE_DEPRECATED:
59             NN_CHECK(NumInputsWithValues(operation, operands) == 3);
60             outputShape->dimensions = {SizeOfDimension(hash, 0)};
61             break;
62         case LSHProjectionType_DENSE: {
63             RunTimeOperandInfo* weight = GetInput(operation, operands, kWeightTensor);
64             NN_CHECK_EQ(NumInputsWithValues(operation, operands), 4);
65             NN_CHECK_EQ(NumDimensions(weight), 1);
66             NN_CHECK_EQ(SizeOfDimension(weight, 0), SizeOfDimension(input, 0));
67             outputShape->dimensions = {SizeOfDimension(hash, 0) * SizeOfDimension(hash, 1)};
68             break;
69         }
70         default:
71             return false;
72     }
73 
74     outputShape->type = OperandType::TENSOR_INT32;
75     outputShape->offset = 0;
76     outputShape->scale = 0.f;
77 
78     return true;
79 }
80 
81 // Compute sign bit of dot product of hash(seed, input) and weight.
82 // NOTE: use float as seed, and convert it to double as a temporary solution
83 //       to match the trained model. This is going to be changed once the new
84 //       model is trained in an optimized method.
85 //
86 template <typename T>
runningSignBit(const RunTimeOperandInfo * input,const RunTimeOperandInfo * weight,float seed)87 int runningSignBit(const RunTimeOperandInfo* input, const RunTimeOperandInfo* weight, float seed) {
88     double score = 0.0;
89     int input_item_bytes = nonExtensionOperandSizeOfData(input->type, input->dimensions) /
90                            SizeOfDimension(input, 0);
91     char* input_ptr = (char*)(input->buffer);
92 
93     const size_t seed_size = sizeof(seed);
94     const size_t key_bytes = seed_size + input_item_bytes;
95     std::unique_ptr<char[]> key(new char[key_bytes]);
96 
97     for (uint32_t i = 0; i < SizeOfDimension(input, 0); ++i) {
98         // Create running hash id and value for current dimension.
99         memcpy(key.get(), &seed, seed_size);
100         memcpy(key.get() + seed_size, input_ptr, input_item_bytes);
101 
102         int64_t hash_signature = farmhash::Fingerprint64(key.get(), key_bytes);
103         double running_value = static_cast<double>(hash_signature);
104         input_ptr += input_item_bytes;
105         if (weight->lifetime == OperandLifeTime::NO_VALUE) {
106             score += running_value;
107         } else {
108             score += static_cast<double>(reinterpret_cast<T*>(weight->buffer)[i]) * running_value;
109         }
110     }
111 
112     return (score > 0) ? 1 : 0;
113 }
114 
115 template <typename T>
SparseLshProjection(LSHProjectionType type,const RunTimeOperandInfo * hash,const RunTimeOperandInfo * input,const RunTimeOperandInfo * weight,int32_t * out_buf)116 void SparseLshProjection(LSHProjectionType type, const RunTimeOperandInfo* hash,
117                          const RunTimeOperandInfo* input, const RunTimeOperandInfo* weight,
118                          int32_t* out_buf) {
119     int num_hash = SizeOfDimension(hash, 0);
120     int num_bits = SizeOfDimension(hash, 1);
121     for (int i = 0; i < num_hash; i++) {
122         int32_t hash_signature = 0;
123         for (int j = 0; j < num_bits; j++) {
124             T seed = reinterpret_cast<T*>(hash->buffer)[i * num_bits + j];
125             int bit = runningSignBit<T>(input, weight, static_cast<float>(seed));
126             hash_signature = (hash_signature << 1) | bit;
127         }
128         if (type == LSHProjectionType_SPARSE_DEPRECATED) {
129             *out_buf++ = hash_signature;
130         } else {
131             *out_buf++ = hash_signature + i * (1 << num_bits);
132         }
133     }
134 }
135 
136 template <typename T>
DenseLshProjection(const RunTimeOperandInfo * hash,const RunTimeOperandInfo * input,const RunTimeOperandInfo * weight,int32_t * out_buf)137 void DenseLshProjection(const RunTimeOperandInfo* hash, const RunTimeOperandInfo* input,
138                         const RunTimeOperandInfo* weight, int32_t* out_buf) {
139     int num_hash = SizeOfDimension(hash, 0);
140     int num_bits = SizeOfDimension(hash, 1);
141     for (int i = 0; i < num_hash; i++) {
142         for (int j = 0; j < num_bits; j++) {
143             T seed = reinterpret_cast<T*>(hash->buffer)[i * num_bits + j];
144             int bit = runningSignBit<T>(input, weight, static_cast<float>(seed));
145             *out_buf++ = bit;
146         }
147     }
148 }
149 
150 template <typename T>
Eval()151 bool LSHProjection::Eval() {
152     NNTRACE_COMP("LSHProjection::Eval");
153 
154     int32_t* out_buf = reinterpret_cast<int32_t*>(output_->buffer);
155 
156     switch (type_) {
157         case LSHProjectionType_DENSE:
158             DenseLshProjection<T>(hash_, input_, weight_, out_buf);
159             break;
160         case LSHProjectionType_SPARSE:
161         case LSHProjectionType_SPARSE_DEPRECATED:
162             SparseLshProjection<T>(type_, hash_, input_, weight_, out_buf);
163             break;
164         default:
165             return false;
166     }
167     return true;
168 }
169 
170 template bool LSHProjection::Eval<float>();
171 template bool LSHProjection::Eval<_Float16>();
172 
173 template int runningSignBit<float>(const RunTimeOperandInfo* input,
174                                    const RunTimeOperandInfo* weight, float seed);
175 template int runningSignBit<_Float16>(const RunTimeOperandInfo* input,
176                                       const RunTimeOperandInfo* weight, float seed);
177 
178 template void SparseLshProjection<float>(LSHProjectionType type, const RunTimeOperandInfo* hash,
179                                          const RunTimeOperandInfo* input,
180                                          const RunTimeOperandInfo* weight, int32_t* outBuffer);
181 template void SparseLshProjection<_Float16>(LSHProjectionType type, const RunTimeOperandInfo* hash,
182                                             const RunTimeOperandInfo* input,
183                                             const RunTimeOperandInfo* weight, int32_t* outBuffer);
184 
185 template void DenseLshProjection<float>(const RunTimeOperandInfo* hash,
186                                         const RunTimeOperandInfo* input,
187                                         const RunTimeOperandInfo* weight, int32_t* outBuffer);
188 template void DenseLshProjection<_Float16>(const RunTimeOperandInfo* hash,
189                                            const RunTimeOperandInfo* input,
190                                            const RunTimeOperandInfo* weight, int32_t* outBuffer);
191 
192 }  // namespace nn
193 }  // namespace android
194