Adb日志想查看Android端侧的日志信息输出,一般采用命令行 adb logcat或Android Stadio中Logcat插件的方式.最近要实现一个Android App的自动测试,所以需要使用真机连接到服务器上运行,因此更多使用命令行输出Logcat的形式.但是Adb Logcat的输出中只包含pid\tid等信息,不包含包名等属性,导致无法过滤来自指定包名所有Activity的log.在Github上翻了下,好像也没有支持Package Name过滤的Logcat客户端.因此决定自己改一个出来.如何获取Package Name?这个问题的解答可能还要从AS的Logcat Plugin的源码入手.这部分功能在Plugin中被称为 ProcessMonitor.具体的代码仓库位于这里.这个功能由两部分组成,运行在端侧的Agent(C++编写),运行在Server端的AgentTracker(来采集并缓存ProcessName与Pid的映射)以及管理Agent运行.端侧的Agent代码十分简单,只是一个loop来从procfs中获取进程信息,并从cmdline文件中截断出文件名.在loop中不断轮询/proc下所有pid,并与缓存的pid set进行比较,来输出pid新增或减少情况.Server端的Tracker根据Agent的输出来更新pid与ProcessName(在Zygote启动的Java App子进程中,这应当是包名). /** * Reads processes from "/proc" and retrieves their name from * "/proc/<pid>/cmdline" and prints: When a process is added: "+ <pid> * <process-name>" When a process is removed: "- <pid>" New processes are * added to the processes set and processes that not longer exists are removed * from it. */ void scanProcesses() { // Whatever is left in this set needs to be removed from ::processes set<int> markedForRemoval(processes); DIR* pDir = opendir("/proc"); while (true) { dirent* pDirent = readdir(pDir); if (pDirent == nullptr) { break; } int pid = parseInt(pDirent->d_name, -1); // Ignore entries that are not a valid pid if (pid < 0) { continue; } markedForRemoval.erase(pid); if (processes.find(pid) != processes.end()) { continue; } // New process found string path = string("/proc/") + pDirent->d_name; const string& name = readCommand(path); if (name.empty() || startsWith(name, "zygote") || name == "<pre-initialized>") { // Ignore processes without a name or that haven't initialized yet continue; } processes.insert(pid); printf("+ %d %s\n", pid, name.c_str()); } closedir(pDir); for (const int pid : markedForRemoval) { processes.erase(pid); printf("- %d\n", pid); } ::fflush(stdout); }这样实现确实比较简单,但是感觉并不算优雅.AS作为第一方的App可以采用这种设计,但是如果要设计一个第三方实现,在端侧启动一个Forever Loop应用程序似乎并不太合适.翻了下老版本的实现,发现有注释提到可以用 ps aux 来提取ProcessName.(这样的另一个好处是避免了权限问题,而且某些命令行服务在cmdline文件中可能是以全路径的格式保存,还要进一步分割).成品在Github上翻找一通,只找到了一个6年前的Rust项目rogcat 大致符合我的要求,奈何依赖库太老,甚至Tokio都还没有正式版.按照他的思路(使用nom处理logcat的原输出,Stream处理流式输出)仿了一个精简版:如果你感兴趣,也可以在这里找到这个简陋的项目.
内存分配MNN中有三种内存分配器：DefaultAllocator,BufferAllocator RecurseAllocator.Recurse分配器,实际上只是BufferAlloator的简单封装,因此这里我们只讨论前两种.DefaultAllocatorclass DefaultAllocator : public BufferAllocator::Allocator { public: DefaultAllocator() { // Do nothing } virtual ~ DefaultAllocator() { // Do nothing } virtual std::pair<void*, size_t> onAlloc(size_t size, size_t align) { return std::make_pair(MNNMemoryAllocAlign(size, MNN_MEMORY_ALIGN_DEFAULT), 0); } virtual void onRelease(std::pair<void*, size_t> ptr) { MNN_ASSERT(ptr.second == 0); MNNMemoryFreeAlign(ptr.first); } };DefaultAllocator提供了底层的malloc 实现,并提供了基本的内存对齐功能.onAlloc生成一个Pair\<内存指针,0>MNNMemoryAllocAlign的实现如下:static inline void **alignPointer(void **ptr, size_t alignment) { return (void **)((intptr_t)((unsigned char *)ptr + alignment - 1) & -alignment); } extern "C" void *MNNMemoryAllocAlign(size_t size, size_t alignment) { MNN_ASSERT(size > 0); #ifdef MNN_DEBUG_MEMORY return malloc(size); #else void **origin = (void **)malloc(size + sizeof(void *) + alignment); MNN_ASSERT(origin != NULL); if (!origin) { return NULL; } void **aligned = alignPointer(origin + 1, alignment); aligned[-1] = origin; return aligned; #endif }首先,(void **)malloc(size + sizeof(void *) + alignment) 用于分配原始内存,sizeof(void*)是用于存储origin地址,即 aligned[-1] = origin, 多申请alignment是保证对齐之后仍然最少有size内存,强转成(void* )是为了传给alignPointer时直接+1跳过开始的部分保留给以后.alignPointer的实现是为了将地址对齐(这块上古魔术转换我也不太理解,看上去是NCNN的时代就在用了)BufferAllocatorBufferAllocator的用途在于池化内存,每块内存优先从池中分配,释放内存时回归内存池.核心逻辑如下:std::pair<void*, size_t> BufferAllocator::alloc(size_t size, bool separate, size_t align) { #ifdef DUMP_USAGE auto memoryUsed = size / 1024.0f / 1024.0f; MNN_PRINT("Alloc: %f\n", memoryUsed); #endif if (0 == align) { align = mAlign; } std::pair<void*, size_t> pointer; // reuse if possible if (!separate) { if (nullptr != mCurrentFreeList) { pointer = getFromFreeList(mCurrentFreeList, size, false, align); } if (nullptr != pointer.first) { return pointer; } pointer = getFromFreeList(&mFreeList, size, true, align); if (nullptr != pointer.first) { return pointer; } } // alloc otherwise pointer = mAllocator->onAlloc(size, align); if (nullptr == pointer.first) { return pointer; } mTotalSize += size; // save node SharedPtr<Node> node(new Node); node->size = size; node->pointer = pointer; mUsedList[pointer] = node; node->outside = mAllocator.get(); MNN_ASSERT(pointer.second % align == 0); #ifdef DUMP_USAGE MNN_PRINT("mTotalSize: %f\n", mTotalSize / 1024.0f / 1024.0f); #endif return pointer; } 当申请分配内存时,Allocator首先从自己的线程中的mCurrentFreeList空闲列表中获取(这是出于多线程数据竞争考虑),若取不到,再从全局的mFreeList中获取. 取出池中的内存的逻辑为给定一个内存大小数目,返回内存池列表(<Size, Node>)中Size大于指定内存的节点.另外还应思考一个问题,池中的内存的Align可能与请求的不同,因此应当对这种情况做出考量并修正内存地址.从池中取出内存后,Allocator还会检查余下的空间是否足够再次分配,如果不足够或指定不允许再次分配内存,则直接返回.如果允许Split,则将父节点切分成两个子节点,将符合要求的一份子节点返回,剩下一份空闲内存块保留.需要考虑节点有父节点的情况,因此在切分子节点时增加父节点引用计数.当子节点被回收时,减小引用计数.当引用计数归0时,即表明所有子节点都已被回收,被切分的父节点会回归整块.std::pair<void*, size_t> BufferAllocator::getFromFreeList(FREELIST* list, size_t size, bool permiteSplit, size_t align) { size_t realSize = size; bool needExtraSize = mAlign % align != 0; if (needExtraSize) { realSize = size + align - 1; } // get node larger than size auto x = list->lower_bound(realSize); // if (x == list->end()) { return std::make_pair(nullptr, 0); } auto pointer = x->second->pointer; // Align offset if (needExtraSize) { size_t originOffset = pointer.second; pointer.second = UP_DIV(originOffset, align) * align; //计算Align后的内存地址 realSize = size + pointer.second - originOffset; // 计算Align后的Size } if (permiteSplit && nullptr != x->second->parent.get()) { x->second->parent->useCount += 1; } // uses up all aligned space auto sizeAlign = UP_DIV(realSize, mAlign) * mAlign; //下一个mAlign后的内存大小 if (sizeAlign >= x->first || (!permiteSplit)) { mUsedList.insert(std::make_pair(pointer, x->second)); list->erase(x); MNN_ASSERT(pointer.second % align == 0); return pointer; } // split otherwise SharedPtr<Node> first(new Node); first->parent = x->second; first->size = sizeAlign; first->pointer = x->second->pointer; mUsedList.insert(std::make_pair(pointer, first)); x->second->useCount += 1; //将x->second作为父节点,生成新的内存块,内存起始为父节点内存尾地址的下一个mAlign. SharedPtr<Node> second(new Node); second->parent = x->second; second->size = x->second->size - sizeAlign; second->pointer.first = x->second->pointer.first; second->pointer.second = x->second->pointer.second + sizeAlign; list->erase(x); //将内存块插入池中 list->insert(std::make_pair(second->size, second)); MNN_ASSERT(pointer.second % align == 0); return pointer; }MNN将分配的小块内存封装为Node,Node携带了内存大小,指向内存的指针,父对象和分配器等信息.其中parent是指向此块内存从哪个大块内存中切割出来(若有),useCount则表示此内存所有子内存的分配情况. class Node : public RefCount { public: ~Node(); std::pair<void*, size_t> pointer; SharedPtr<Node> parent = nullptr; size_t size; size_t useCount = 0; Allocator* outside = nullptr; };当某块内存被Free时,会将node从UsedList中转移到FREELIST并调用Allocator的returnMemory逻辑,先检测父节点的useCount是否为0,如果为0,则依次从子元素开始回收子节点,将list中所有父元素的子节点都删除,并将父节点放回freelist,同时再向上检测在上一级内存的RefCount情况.void BufferAllocator::returnMemory(FREELIST* listP, SharedPtr<Node> node, bool permitMerge) { auto& list = *listP; list.insert(std::make_pair(node->size, node)); // update parent use count if (nullptr != node->parent.get() && permitMerge) { auto parent = node->parent; parent->useCount -= 1; // merge if all subnodes were freed auto needMerge = parent->useCount == 0; while (needMerge) { // collect all subnodes for (auto iter = list.begin(); iter != list.end();) { if (iter->second->parent.get() == parent.get()) { iter = list.erase(iter); continue; } iter++; } // do merge downside up list.insert(std::make_pair(parent->size, parent)); needMerge = false; if (parent->parent.get() != nullptr) { parent = parent->parent; parent->useCount -= 1; needMerge = parent->useCount == 0; } } } }
Version: Commit 5488fb78Feature: x86_64 CPU Only, mmap,no blas. 略过了所有有关KV缓存的部分.以下文字可能因代码更新或本人认知水平而不再适用.LLaMA.cpp or GGMLGGML是LLaMa.cpp同一作者的作品,作者将LLaMa和Whisper等cpp实现库中用到的运算相关函数提取到了一个库中,命名为GGML(A Tensor Lib for ML), 因此GGML并不是类似MNN等的推理框架,而仅仅是一个操作算子的加速计算库而已,有关模型序列化\子图划分等上层功能仍要由调用方实现,因此这里还是选择阅读LLaMa.cpp的代码,来梳理一个简单的推理库要做什么工作.Weights File StructrueLLama.cpp(下文简称Lc)没有像其他ML框架一样借助Proto或者FlatBuf这种序列化框架来实现权重的序列化，而是简单采用二进制顺序读写来自定义序列化，比起框架方案缺少了向前兼容和透明迁移等特性，但是毫无疑问简单了很多。下面介绍文件结构:第一个 u32 是Magic Number，用于识别文件格式与版本类型(LLAMA_FILE_VERSION_GGMF_V1 ,LLAMA_FILE_VERSION_GGJT_V1 etc.) ，具体可参考下面的enum.enum llama_file_version { LLAMA_FILE_VERSION_GGML, LLAMA_FILE_VERSION_GGMF_V1, // added version field and scores in vocab LLAMA_FILE_VERSION_GGJT_V1, // added padding LLAMA_FILE_VERSION_GGJT_V2, // changed quantization format LLAMA_FILE_VERSION_GGJT_V3, // changed Q4 and Q8 quantization format };接下来的7个u32是模型的参数，如layer数目,head数目等，是与模型类型紧密结合的，此外还有一个n_vocab 参数，用于决定接下来的vocab存储的数目。再接下来LLama.cpp会从文件中读取vocab，每个vocab由字符串长度len(u32) vocab字符串word(string 长度为len) score (float) 组成,并被按顺序从文件中依次读出.vocab表读取完之后,文件剩下的部分就是Tensor Map了,Lc使用一个while循环一直读到文件末尾来读取出所有的Tensor信息(包括名称和权重).每个Tensor的存储格式为维度数目n_nums(u32) 名称长度 name_len(u32) Tensor type(u32) Tensor 维度数组(长为n_nums的u32数组,记录了每一维的大小 Tensor名称(长为name_len的字符串 ,读出以上metadata之后,如果文件存储格式版本大于LLAMA_FILE_VERSION_GGJT_V1,则metadata之后会有一段padding来对齐到32字节.从下一个32字节开始存储Tensor的weights数据 ,但是在最开始的load过程中不做读取,仅仅计算出应当读取的字节数并记录在llama_load_tensor 结构体中,后期再使用mmap或其他方式读入内存.读取metadata完毕后,会将llama_load_tensor放入一个列表中,并生成一个name_to_tensor_idx的索引便于查找.至此 模型文件的加载就完成了.struct llama_load_tensor { std::string name; enum ggml_type type = GGML_TYPE_F32; std::vector<uint32_t> ne; //维度数据 size_t file_off; //计算在文件中的偏移量 size_t size; //计算字节数 struct ggml_tensor * ggml_tensor = NULL; //指向真正的 可执行计算的 Tensor对象 uint8_t * data; };Lc计算weights的字节数:对于Float32和FP16型的Tensor而言,使用一个相应的Float类型来存储即可,Lc计算出的字节数即为sizeof(float)但是对于量化类型,每个FP32元素会用较低精度的类型来表示(如4bit int),为了弥补精度下降带来的计算误差,必须额外携带纠正数据,因此可能使用一个结构体来存储一组数据.一个典型结构如下: 以Q4_0量化为例,量化后的数据每32个元素分为一个block,每个数据以4bit(半个int8)来存储,占用sizeof(fp16)+sizeof(uint8)*16=18bit 存储,因此n个元素的Tensor占用的字节数目为sizeof(block_q4_0) *n /32 依照此可以算出Tensor的weight在文件中的偏移量.这也是为什么4Bit/8Bit量化可以显著降低内存占用的原因.#define QK4_0 32 typedef struct { ggml_fp16_t d; // delta uint8_t qs[QK4_0 / 2]; // nibbles / quants } block_q4_0; static_assert(sizeof(block_q4_0) == sizeof(ggml_fp16_t) + QK4_0 / 2, "wrong q4_0 block size/padding");int qk =32 for (int j = 0; j < qk/2; ++j) { //同时取两个数字进行存储 const float x0 = x[i*qk + 0 + j]*id; const float x1 = x[i*qk + qk/2 + j]*id; const uint8_t xi0 = MIN(15, (int8_t)(x0 + 8.5f)); const uint8_t xi1 = MIN(15, (int8_t)(x1 + 8.5f)); //分别占据一个uint8的前4位和后四位 y[i].qs[j] = xi0; y[i].qs[j] |= xi1 << 4; }讨论:Lc中的权重格式是高度定制化的,而且也没有数据校验设计,只能用于相对简单且格式更迭不剧烈的情况下.Memory Buffer in GGMLLc与底层GGML各有内存池实现,不过都比较简单,是使用静态数组来作为内存池并且预先分配完成.Lc的内存池为llama_context结构体中的buf_compute buf_scratch* ,类型为llama_buffer.此外,还用llama_model 中的buf(,但仅仅用于存储从文件中读取的权重Tensor结构体信息),llama_context中的work_buffer (算子计算时的中间结果缓冲区,是每个算子进行重用的). Lc创建的内存池都会在不同时期通过以引用形式传递给下层ggml的方式来进行使用,lc本身不进行内存池上对象的分配.GGML的内存池位于ggml_context中的mem_buffer ,此外还有ggml_scratch scratch 来持有上述中llama buf_scratch内存池列表中内存池的引用,便于GGML进行对象的分配.各内存池都随相应的context来进行创建(或引用已有内存池).buf_compute 内存池用于放置推理时生成的对象(ggml_object),内存池的大小在context初始化时就已经决定了,而且没有动态扩容功能.当llama_context加载模型时,会根据模型的类型从预设中取出预定义的buf_compute大小.buf_scratch 内存池在LLAMA_USE_SCRATCH 宏启用后,会用于Tensor中的实际Data数据的分配存储.Lc会维护一个buf_scratch列表,内部包含两个内存池,大小也是预先静态定义的.在推理过程中,Lc会切换两个内存池来存储Tensor Data,如self-attention放置在第1块内存池,而feed-forward层放置在第2块内存池.这样做的设计我还没有理解.以上两个内存池的初始化代码如下:buf_compute.resize(MEM_REQ_EVAL().at(ctx->model.type) + ggml_graph_overhead()); buf_scratch[0].resize(MEM_REQ_SCRATCH0(hparams.n_ctx).at(ctx->model.type)); buf_scratch[1].resize(MEM_REQ_SCRATCH1().at(ctx->model.type));在ggml中的两个内存池指针中,ggml_scratch仅仅为了持有上层框架传入的内存池引用而设计(ggml_set_scratch),ggml不负责其创建和销毁.而mem_buffer 是由ggml来进行维护的.在创建新的ggml_context 时,可以选择传入mem_buffer 的地址来引用预先创建的内存池,或交由ggml来创建指定大小的内存池(仅在创建KV存储部分见到过这种情形).mem_buffer 在启用LLAMA_USE_SCRATCH特性后,仅仅用于存储ggml_object链表和ggml_tensor对象,而ggml_tensor并不实际存储Tensor中的data,data可能会被存储于mmap区域.计算一个模型所需的mem_buffer的方法如下(注意 这仅仅是加载模型所需Tensor的空间大小.运算时的mem_buffer会指向lc的buf_compute 内存池,计算图和计算Tensor都在其中分配):void calc_sizes(size_t * ctx_size_p, size_t * mmapped_size_p) const { *ctx_size_p = *mmapped_size_p = 0; for (const llama_load_tensor & lt : tensors_map.tensors) { *ctx_size_p += sizeof(struct ggml_tensor) + GGML_OBJECT_SIZE; *(use_mmap ? mmapped_size_p : ctx_size_p) += lt.size + 16; //如果开启mmap,实际上ctx中的mem_buffer就不需要存储Tensor中的数据. } }我们借助一个Tensor的创建过程来实际描述Lc中内存池的使用:static struct ggml_tensor * ggml_new_tensor_impl( struct ggml_context * ctx, enum ggml_type type, int n_dims, const int64_t* ne, void* data) { size_t data_size = 0; if (data == NULL && !ctx->no_alloc) { //no_alloc只有在非CPU后端时才会为true data_size += GGML_TYPE_SIZE[type]*(ne[0]/GGML_BLCK_SIZE[type]); for (int i = 1; i < n_dims; i++) { data_size *= ne[i]; } } if (ctx->scratch.data != NULL && data == NULL) { // allocate tensor data in the scratch buffer if (ctx->scratch.offs + data_size > ctx->scratch.size) { GGML_PRINT("%s: not enough space in the scratch memory pool (needed %zu, available %zu)\n", __func__, ctx->scratch.offs + data_size, ctx->scratch.size); assert(false); return NULL; } data = (char * const) ctx->scratch.data + ctx->scratch.offs; ctx->scratch.offs += data_size; data_size = 0; } struct ggml_object * const obj_new = ggml_new_object(ctx, GGML_OBJECT_TENSOR, GGML_TENSOR_SIZE + data_size); struct ggml_tensor * const result = (struct ggml_tensor *)((char *)ctx->mem_buffer + obj_new->offs); *result = (struct ggml_tensor) { /*.type =*/ type, /*.backend =*/ GGML_BACKEND_CPU, /*.n_dims =*/ n_dims, /*.ne =*/ { 1, 1, 1, 1 }, /*.nb =*/ { 0, 0, 0, 0 }, /*.op =*/ GGML_OP_NONE, //GGML_OP_NONE代表constant Tensor 不执行任何计算. // ... something we do not care!... /*.data =*/ (data == NULL && !ctx->no_alloc) ? (void *)(result + 1) : data, /*.name =*/ { 0 }, //注意 这里的名字也是空白的,等待后续使用set_name来命名. }; // TODO: this should not be needed as long as we don't rely on aligned SIMD loads //ggml_assert_aligned(result->data); for (int i = 0; i < n_dims; i++) { result->ne[i] = ne[i]; } result->nb[0] = GGML_TYPE_SIZE[type]; result->nb[1] = result->nb[0]*(result->ne[0]/GGML_BLCK_SIZE[type]); for (int i = 2; i < GGML_MAX_DIMS; i++) { result->nb[i] = result->nb[i - 1]*result->ne[i - 1]; } ctx->n_objects++; return result; }在 ggml_new_tensor_impl 中,当要求创建一个Tensor且没有为它传入data指针时,证明需要创建一个指定维度的空白Tensor.首先ggml根据维度数据计算出内部的data所需的内存大小.当启用了LLAMA_USE_SCRATCH后,data会被分配到scracth内存池中.如果内存池空间不足,则直接报错退出,没有扩容操作.scracth内存池为很简单的offset模型,获取一定长度的内存创建data后,增加已经使用的offset数值即可.ggml_new_object 函数用于维护ggml_object 链表,内容如下:static struct ggml_object * ggml_new_object(struct ggml_context * ctx, enum ggml_object_type type, size_t size) { // always insert objects at the end of the context's memory pool struct ggml_object * obj_cur = ctx->objects_end; const size_t cur_offs = obj_cur == NULL ? 0 : obj_cur->offs; const size_t cur_size = obj_cur == NULL ? 0 : obj_cur->size; const size_t cur_end = cur_offs + cur_size; // align to GGML_MEM_ALIGN size_t size_needed = GGML_PAD(size, GGML_MEM_ALIGN); char * const mem_buffer = ctx->mem_buffer; struct ggml_object * const obj_new = (struct ggml_object *)(mem_buffer + cur_end); if (cur_end + size_needed + GGML_OBJECT_SIZE > ctx->mem_size) { GGML_PRINT("%s: not enough space in the context's memory pool (needed %zu, available %zu)\n", __func__, cur_end + size_needed, ctx->mem_size); assert(false); return NULL; } *obj_new = (struct ggml_object) { .offs = cur_end + GGML_OBJECT_SIZE, .size = size_needed, .next = NULL, .type = type, }; ggml_assert_aligned(mem_buffer + obj_new->offs); if (obj_cur != NULL) { obj_cur->next = obj_new; } else { // this is the first object in this context ctx->objects_begin = obj_new; } ctx->objects_end = obj_new; //printf("%s: inserted new object at %zu, size = %zu\n", __func__, cur_end, obj_new->size); return obj_new; } //ggml object enum ggml_object_type { GGML_OBJECT_TENSOR, GGML_OBJECT_GRAPH, GGML_OBJECT_WORK_BUFFER }; // ggml object struct ggml_object { size_t offs; size_t size; struct ggml_object * next; enum ggml_object_type type; char padding[4]; };这里是一个标准的链表模式,ctx中记录了object链表的头和尾元素.object元素自身也携带着指向下个元素的指针.但是实际上object本身并不承担任何功能,仅仅为了标记内存池的分配情况.ctx->objects_end 指向了链表的末尾元素,也是当前内存池中最后一个元素.当需要分配新的元素时,通过最后一个元素的首地址(offset)+元素自身大小(size)就可以得到下一个空闲地址在内存池中的位置了.当我们真正要为一个Object(以 ggml_tensor为例子)分配内存时,首先计算出Object所需的内存大小(在这里为 sizeof(ggml_tensor)+ datasize)并进行内存对齐,在加上一个ggml_object 对象的大小,即为需分配的内存大小.从内存池中先创建一个ggml_object ,并写入Object 的offset和size,插入链表并返回.调用者即可利用返回的ggml_object 中的offset内存地址和size来创建上层的Object.此外,所有的内存池数组都已经Aligned,在32位系统上为4bit对齐,64位为16bit对齐.(但是在Metal中可能有不同的对齐方式,这里不做研究),视需要也可能使用mlock来pin住内存.1.这里有个小问题: 如果我们delete了某个池内对象,造成的内存碎片怎么处理呢?答案是:不delete. GGML没有设计delete_object的相关函数(最起码我还没有找到).当GGML不需要一个Tensor的时候,极有可能整张运算图都不需要了,直接把整个context连同Memory Buffer扔掉就好了.Object 链表是拿来做什么的呢?我一开始以为内存池的分配会是类似OS中首次适应算法的设计,但是实际上并没有那么复杂.目前看来 链表的唯一作用是给定Context和Tensor名称的时候可以查找对应的Tensor(但是这个功能看上去完全没有需求,包括Lc本身的examples里面也没有调用这种方案)或者按顺序PPrint Obejcts.Tensor in GGML在GGML中,从Weights文件中反序列化出的Tensor仅仅具有名字,维度和内容所在的文件偏移地址,并不包含模型结构与计算图信息,因此无法参与运算.正如上文所提到的,这种Tensor的类型为llama_load_tensor ,仅仅用于读取模型时候使用.在model加载完毕后,lc会根据tensor_map 中的大小来分配内存池.分配完成后,则开始根据事先硬编码的Tensor名称来查询并为llama_load_tensor 创建真正的Tensor,包括norm等层的权重向量,model的output等.创建过程类似上文所述ggml_new_tensor_impl .[参见 llama.cpp line_{1164,1224}].Tensor全部创建完成之后,lc会从文件中加载实际Tensor的data. 加载过程如下:void load_data_for(llama_load_tensor & lt) { if (use_mmap) { lt.data = (uint8_t *) mapping->addr + lt.file_off; //根据文件偏移值直接从mmap中读出data起始地址 } else { llama_file & file = file_loader->file; file.seek(lt.file_off, SEEK_SET); file.read_raw(lt.data, lt.size);//若未启用mmap,lt.data为uint8数组,从文件中拷贝进去 }若启用了mmap,则不需要手动进行读入,只需要计算出mmap后的地址赋值即可,此外根据Tensor位于的Backend不同,加载data后也执行不同操作,CPU backend会使用Mlock来Pin住这一块data的内存,防止被换页造成性能损耗,GPU会转移到对应的硬件内存中并释放data内存.ggml_tensor的结构如下:struct ggml_tensor { enum ggml_type type; //数据类型 FP32 FP16 or Quant enum ggml_backend backend; //位于的计算后端 int n_dims; // N维矩阵 int64_t ne[GGML_MAX_DIMS]; // number of elements of each dim size_t nb[GGML_MAX_DIMS]; // stride in bytes: // nb[0] = sizeof(type) // nb[1] = nb[0] * ne[0] + padding // nb[i] = nb[i-1] * ne[i-1] // stride用来快速通过维度坐标取出底层元素 // compute data enum ggml_op op; // Operation Code,标明这个向量是什么操作的运算结果 // op params - allocated as int32_t for alignment int32_t op_params[GGML_MAX_OP_PARAMS / sizeof(int32_t)]; bool is_param; //用于标识Trainable的(猜测) Infer用不到 struct ggml_tensor * grad; //梯度Tensor 记录反向传播用的 在Infer用不到 struct ggml_tensor * src[GGML_MAX_SRC]; // Tensor在图中的数据来源,即OP的运算数 // performance 性能benchamrk用的 int perf_runs; int64_t perf_cycles; int64_t perf_time_us; // 底层数组 void * data; char name[GGML_MAX_NAME]; void * extra; // extra things e.g. for ggml-cuda.cu // 没找到干嘛的↓ char padding[4]; };在模型的运算(Inference)中,大部分框架遵循的一个基本的模式即为数据流从Input 开始流动,(Input可能是模型的输入Tensor,也可能是权重文件中固化的Weights常量,也可能是配置常量),流经Operation节点对数据进行操作,并输出新的数据,新的数据沿着计算图设定好的模型结构继续流向下一个Operation节点,最终直至流到输出节点进行结果输出.每个Operation通常不止一个Input(一般有一个或多个来自模型输入的变量Tensor,也有多个常量作为Weights来参与计算),但一般情况下可能只有一个Output(::反正Lc只考虑了有一个Output的情况,在不考虑RNN\LSTM这些算子和控制流的情况下,大概也是够用的?::).因此 Lc的Tensor做出了以下设计:Tensor为Constant,在模型中可能对应权重常量或模型输入,仅作为Operation的数据来源,不执行计算,op属性为GGML_OP_NONE ,src为{NULL}.在计算图中处于叶子结点.其data属性即为携带的底层内容数据.Tensor为Intermediate Tensor ,即计算节点.为了实现方便,Lc中的Operation与此Operation计算的结果都存储在此Tensor中.此Tensor会执行op属性的算子计算,计算所需的操作数为src属性指向的多个Tensor id,计算得出的结果为data属性所指向的数据. op_params属性为执行计算所需的其他parameter.通过src属性,每个计算Tensor都可以找到自己的数据源Tensor,同时也会被下一级计算的Tensor引用,直到追溯到Constant,这便组成了一个DAG计算图.Lc在执行阶段便沿着这条计算图来进行计算和数据流动.Computation Graph参见Lc中的llama_eval_internal 函数,在约{1488->1715}行,使用CPP代码手动构建了一遍LLaMa的结构模型,包括norm,self-Attention,feed_forward等部分.至此,DAG算子图建立完毕.但是仅仅有算子之间的关联并不足以构建执行模型所需的执行顺序等信息,ggml通过ggml_cgraph 来创建执行模型的计算顺序信息. ggml_cgraph 的结构如下:// computation graph struct ggml_cgraph { int n_nodes; int n_leafs; struct ggml_tensor * nodes[GGML_MAX_NODES]; struct ggml_tensor * grads[GGML_MAX_NODES]; struct ggml_tensor * leafs[GGML_MAX_NODES]; void * visited_hash_table[GGML_GRAPH_HASHTABLE_SIZE]; // performance int perf_runs; int64_t perf_cycles; int64_t perf_time_us; };ggml通过ggml_build_forward_expand 函数来通过Tensor组成的DAG图来生成计算图,阅读下ggml_build_forward_impl 的核心代码就知道,这是个典型的拓扑排序.static void ggml_build_forward_impl(struct ggml_cgraph * cgraph, struct ggml_tensor * tensor, bool expand) { if (!expand) { cgraph->n_nodes = 0; cgraph->n_leafs = 0; } const int n0 = cgraph->n_nodes; UNUSED(n0); ggml_visit_parents(cgraph, tensor); const int n_new = cgraph->n_nodes - n0; GGML_PRINT_DEBUG("%s: visited %d new nodes\n", __func__, n_new); if (n_new > 0) { // the last added node should always be starting point GGML_ASSERT(cgraph->nodes[cgraph->n_nodes - 1] == tensor); } } static void ggml_visit_parents(struct ggml_cgraph * cgraph, struct ggml_tensor * node) { if (node->grad == NULL) { // this usually happens when we generate intermediate nodes from constants in the backward pass // it can also happen during forward pass, if the user performs computations with constants if (node->op != GGML_OP_NONE) { //GGML_PRINT_DEBUG("%s: warning: node %p has no grad, but op %d\n", __func__, (void *) node, node->op); } } // check if already visited if (hash_insert(cgraph->visited_hash_table, node)) { return; } for (int i = 0; i < GGML_MAX_SRC; ++i) { if (node->src[i]) { ggml_visit_parents(cgraph, node->src[i]); } } if (node->op == GGML_OP_NONE && node->grad == NULL) { // reached a leaf node, not part of the gradient graph (e.g. a constant) GGML_ASSERT(cgraph->n_leafs < GGML_MAX_NODES); if (strlen(node->name) == 0) { ggml_format_name(node, "leaf_%d", cgraph->n_leafs); } cgraph->leafs[cgraph->n_leafs] = node; cgraph->n_leafs++; } else { GGML_ASSERT(cgraph->n_nodes < GGML_MAX_NODES); if (strlen(node->name) == 0) { ggml_format_name(node, "node_%d", cgraph->n_nodes); } cgraph->nodes[cgraph->n_nodes] = node; cgraph->grads[cgraph->n_nodes] = node->grad; cgraph->n_nodes++; } }这个拓扑排序保证了以下几点:nodes数组中的元素应当都是计算Tensor.leafs数组中应当都是常量.nodes数组中的元素索引从小到大按照拓扑顺序排序的,这也就意味着某个计算Tensor所依赖的所有数据源Tensor一定在nodes数组中排在此Tensor之前.当GGML按照nodes索引从小到大的顺序依次执行计算Tensor时,保证了每个Tensor的数据源一定已经计算完毕了,从而避免了复杂的依赖问题.成功构建计算图后,GGML通过ggml_graph_compute_helper 函数来编排执行顺序ggml_cplan .这个执行plan更多的是根据算子类型来考虑每个算子能否拆分成多线程并行操作,并计算每个算子计算过程中所需要多少内存,因为算子计算过程中的中间结果会存储在work_buffer 中,因此这些内存需求的最大值会决定work_buffer 的大小.最后,在ggml_graph_compute 函数中,GGML会创建多个线程,分别执行ggml_graph_compute_thread 计算函数来多线程推理模型,他们之间通过 ggml_compute_state_shared 的引用来共享状态.struct ggml_compute_state_shared { const struct ggml_cgraph * cgraph; //计算图 const struct ggml_cplan * cplan; //执行计划,负责提供执行过程中的Context,包含中间变量的内存池,那些算子可以多线程并行,以及cancel_callback. int64_t perf_node_start_cycles; int64_t perf_node_start_time_us; const int n_threads; // synchronization primitives 用于线程间状态同步 atomic_int n_active; // num active threads atomic_int node_n; // active graph node bool (*abort_callback)(void * data); // abort ggml_graph_compute when true void * abort_callback_data; };而ggml_graph_compute_thread 的核心思想即为: 所有线程共同计算一个算子(假设这个算子可以多线程并行).在线程执行的最开始,每个线程都会去查询计算图中的算子列表,并尝试从0开始执行.当取出第一个计算算子后,线程会首先执行算子的INIT子任务.大部分算子的INIT 子任务是空白的,但也有些是初始化内存等操作.(注意,此时可能所有线程都会执行第一个算子的INIT子任务,不过这种任务一般不会有副作用)INIT执行完毕后,线程会检查此算子能否并行执行,如果不能,则会自己完成算子的COMPUTE 子任务,即实际上的算子计算任务.如果可以并行执行,那么他会尝试将任务分配给cplan规划的指定数目的进程,即设置共享状态.:共享状态(简述为State)中n_active值为应当并行的线程数目, node_n为当前计算的算子ID.并开始执行自身分配到的一部分并行计算工作.如果某个线程先完成了自己的一份计算工作,则他会将State中的n_active -1(Atomically),并挂起等待,直到node_n变更,代表下一个可以并行的算子计算工作的开始.当此算子最后一块计算工作也被完成时,线程在-1时发现自己为最后一个完成的线程,会执行算子的Finalize 子任务,即收集结果等,同样也不是所有任务的Finalize都有内容.最后一个进程执行Finalize 完毕后,他会检查下一个算子能否并行并执行INIT,若不能并行,则自己完成计算任务后继续检查下一个算子,直到某个算子可以多线程并行,此时跳转到第三步并依次循环.static thread_ret_t ggml_graph_compute_thread(void * data) { struct ggml_compute_state * state = (struct ggml_compute_state *) data; const struct ggml_cgraph * cgraph = state->shared->cgraph; const struct ggml_cplan * cplan = state->shared->cplan; const int * n_tasks_arr = cplan->n_tasks; const int n_threads = state->shared->n_threads; set_numa_thread_affinity(state->ith, n_threads); int node_n = -1; while (true) { // 判断是否调用callback取消了推理 if (cplan->abort_callback && cplan->abort_callback(cplan->abort_callback_data)) { state->shared->node_n += 1; return (thread_ret_t) GGML_EXIT_ABORTED; } if (atomic_fetch_sub(&state->shared->n_active, 1) == 1) { // all other threads are finished and spinning // do finalize and init here so we don't have synchronize again struct ggml_compute_params params = { /*.type =*/ GGML_TASK_FINALIZE, /*.ith =*/ 0, /*.nth =*/ 0, /*.wsize =*/ cplan->work_size, /*.wdata =*/ cplan->work_data, }; if (node_n != -1) { /* FINALIZE */ struct ggml_tensor * node = state->shared->cgraph->nodes[node_n]; if (GGML_OP_HAS_FINALIZE[node->op]) { params.nth = n_tasks_arr[node_n]; ggml_compute_forward(&params, node); } ggml_graph_compute_perf_stats_node(node, state->shared); } // distribute new work or execute it direct if 1T while (++node_n < cgraph->n_nodes) { GGML_PRINT_DEBUG_5("%s: %d/%d\n", __func__, node_n, cgraph->n_nodes); struct ggml_tensor * node = cgraph->nodes[node_n]; const int n_tasks = n_tasks_arr[node_n]; state->shared->perf_node_start_cycles = ggml_perf_cycles(); state->shared->perf_node_start_time_us = ggml_perf_time_us(); params.nth = n_tasks; /* INIT */ if (GGML_OP_HAS_INIT[node->op]) { params.type = GGML_TASK_INIT; ggml_compute_forward(&params, node); } if (n_tasks == 1) { // TODO: maybe push node_n to the atomic but if other threads see n_tasks is 1, // they do something more efficient than spinning (?) params.type = GGML_TASK_COMPUTE; ggml_compute_forward(&params, node); if (GGML_OP_HAS_FINALIZE[node->op]) { params.type = GGML_TASK_FINALIZE; ggml_compute_forward(&params, node); } ggml_graph_compute_perf_stats_node(node, state->shared); } else { break; } if (cplan->abort_callback && cplan->abort_callback(cplan->abort_callback_data)) { break; } } atomic_store(&state->shared->n_active, n_threads); atomic_store(&state->shared->node_n, node_n); } else { // wait for other threads to finish const int last = node_n; do { //sched_yield(); node_n = atomic_load(&state->shared->node_n); } while (node_n == last); } // check if we should stop if (node_n >= cgraph->n_nodes) break; /* COMPUTE */ struct ggml_tensor * node = cgraph->nodes[node_n]; const int n_tasks = n_tasks_arr[node_n]; struct ggml_compute_params params = { /*.type =*/ GGML_TASK_COMPUTE, /*.ith =*/ state->ith, /*.nth =*/ n_tasks, /*.wsize =*/ cplan->work_size, /*.wdata =*/ cplan->work_data, }; if (state->ith < n_tasks) { ggml_compute_forward(&params, node); } } return GGML_EXIT_SUCCESS; }当所有算子都执行完毕(node_n数目大于等于graph中算子数目)后,线程退出.GGML取出output Tensor的结果,执行完毕.以上就是Lc的Inference过程的大致思路,但是还有一些细节有待探究(GPU Offload的转移,KV的使用等).Lc in 1 Weekend?为什么LLama.cpp能在短短一个周末的时间写完?我认为除了作者对于MLSys很深的了解和基础外,Lc的很多设计实际上被大幅简化了,从而大幅度减少了设计和实现的工作量:Memory Pool为静态且不回收. Lc通过模型的类型直接从预设的几种常数中选取出内存池的大小,内存池为最简单的Offset模型,且没有动态扩容功能.内存池中的Object仅可创建,不可销毁.模型结构为预先定义且不可变.这实际上免去了大部分推理框架所面临的麻烦: 模型结构预定义,则不需要考虑计算图的有效性,不需要编写很多算子,甚至反序列化权重的时候都能心中有数.不需要从第三方模型格式转换,也避免了很多容错和算子转换代码.Transformer结构模型自身的算子比较简单,多为线性计算,相比RNN等复杂算子,实现和优化起来的难度大大减小,也没有单算子多个输出的问题. 同样 NLP模型可以完全把NHWC和NCHW的问题抛到一边.Lc面向的是Cuda和Metal,两者都有较为完善的生态支持,不存在某些算子无法被计算的问题,但是这点在移动端的加速推理场景中经常遇见,不得不采用分割子图等方式规避,实际上带来了很高的工作量.
Intro最近遇到了一个问题:一个基于Distilbert模型Fine-Tune过的模型在NPU上表现很差，推理平均时间远高于GPU，甚至于CPU拉不开差距。测试设备是Google Pixel 7Pro，搭载了Google自研TPU。网络上关于移动边缘侧推理性能的Issue很多，但是牵扯到NPU异构加速的Issue基本上很难有个清晰的解决方案，常见的情形是放弃NPU方案或者更换模型碰碰运气(淦我怎么老是在搞这些没有人搞的破活)。很遗憾在这里两个摆烂方案都不可行，好在一番东翻西找之后解决了问题，将解决方案记录在这里，也给可能有类似问题的后来者一个参考。NNAPI众所周知，随着设备端侧算力的不断加强和诸如隐私计算等政治正确要求的出现，越来越多的MLSys开始注重将Inference(甚至Training)迁移到设备侧。除传统的CPU推理外，越来越多的异构加速模块也开始加入战场，如GPU、DSP甚至厂商定制化的专用加速单元(他们有个好听的名字叫做神经网络运算单元NPU)。高度定制化的加速单元在针对性的模型和算子上可以达到非常高的性能，但想要让加速单元能较好的推理特定的DL模型需要额外的适配和测试工作（如高通NPU(在865之前叫做DSP)只能接受Int8的模型Tensor推理,而华为Kirin的NPU在Float32 Tensor上的性能最好,Google Tensor自研TPU的具体信息更是完全黑盒)。好消息是，面对如此百花齐放又千奇百怪的异构加速单元，Android系统引入了一层虚拟层来封装这些差异，称为(Neural Network API,NNAPI)；坏消息是，NNAPI的版本必须随Android大版本一并更新(因此碎片化现状也不可避免)，而且NNAPI本意是作为DL Framework（如TFLite MNN）等的一个计算后端来设计，因此API十分low-level，文档也过于简洁(见此),给开发者调试的过程带来了很多困难。一个简单的模型推理的调用流程图如图所示，App通过加载ML Lib来运行模型，ML Lib（如TFLite)会视模型内算子的类型将模型分为几个子图，分配的原则是一方面每个子图尽可能大（减少图中运算数据在不同计算后端之间拷贝的时间损耗），另一方面尽可能利用更快的加速单元(若有些算子在GPU和CPU上同样有实现，优先GPU上的加速实现，但如果仅在CPU上有实现，就只能Fallback到CPU上进行运算，同时为了保证第一条，还可能将几个不兼容算子（连同中间夹杂的少数兼容算子）一同Fallback到CPU)。而假设某个子图被判定为NNAPI兼容，则会被分派到NNAPI的运行时上执行，NNAPI会再次进行分割，按照上文类似的方式将算子分配到合适的硬件HAL上真正执行。如上段所示，如果我们不考虑硬件算子实现上出现的Bug，那一个模型如果在NPU上运行不佳的原因可能是：由于大部分算子不兼容NPU，因此被调度到CPU上进行运算，此时NPU的加速性能并没有被很好发挥 –> 这种情况下似乎很难有较好的解决办法，幸运的情况下不兼容算子可以使用其他兼容算子进行组合替代(如MatMul其实是由多个FullyConnected进行组合而成)，不幸运的情况下就只能放弃或者对模型进行大修，如本人曾经在早期尝试过在GPU上对RNN进行推理，彼时只能因为硬件不支持作罢。大部分算子兼容NPU，但是由于几个频繁出现的算子不兼容NPU，导致子图被分割得很碎片化，异构后端之间数据拷贝的Tradeoff太高，导致推理时延过高。这是我猜想本例中更可能出现的情形，也是有相对简单的解决方案的情形：视模型来尝试替换算子，将少数算子去掉或更换。NPU配置问题，查阅资料查找如NPU支持的量化类型不符合或模型是否过大等问题，此外还应当注意，Dynamic Shape Input类型的模型（即输入Shape为(None,X,X)的类型）截止目前可能能不支持。日志追踪对于一个黑盒系统，我们首先能做的只能是去查看运行日志。对于TFLite框架，我建议使用自带的Benchmark Tools尝试运行模型测试，首先去除App调用错误的乌龙。传入--use_nnapi=1 --nnapi_allow_fp16=true --nnapi_accelerator_name=google-edgetpu 来允许Benchmark自动量化模型、启用NNAPI并指定NPU运行。在指定NPU后，所有NPU无法执行的算子就不会调度到NNAPI层，而是有TFLite自行分配到CPU上运行，这有利于我们后面进行的Operation Profiling. Benchmark的结果与一开始类似，NPU的推理平均时延在600ms左右，与我预计的数据(<100ms)相去甚远。好在Benchmark给出了一条很重要的提示:VERBOSE: Replacing 1965 out of 3220 node(s) with delegate (TfLiteNnapiDelegate) node, yielding 64 partitions for the whole graph.这条提示说明仅有一半左右的算子被分配给了NNAPI，整个模型被切分成了64块子图。根据我个人的经验，一般子图数目在小于20个左右比较合适，大于100个时效果就会变得极差，大量时间被数据拷贝消耗了。然而让我疑惑的是，Transformer模型的大部分算子都是线性，不应当出现这么多NPU无法支持的操作才对，于是我进一步进行分析，传入--enable_op_profiling=true开启对每个算子的详细信息进行输出，输出可能会非常冗长，建议转储到文件分析。=============== Summary by node type ============================== [Node type] [count] [avg ms] [avg %] [cdf %] [mem KB] [times called] FULLY_CONNECTED 1190 405.132 72.506% 72.506% 0.000 1190 TfLiteNnapiDelegate 32 141.459 25.317% 97.822% 0.000 32 Add (ND, F32) 3 4.453 0.797% 98.619% 0.000 13 MEAN 26 3.664 0.656% 99.275% 0.000 26 Squared Difference (NC, F32) 1 2.552 0.457% 99.732% 0.000 13 Copy (NC, X32) 1 1.285 0.230% 99.962% 0.000 7 Convert (NC, QS8, F32) 1 0.161 0.029% 99.991% 0.000 1 GATHER 1 0.041 0.007% 99.998% 0.000 1 Fully Connected (NC, F32) GEMM 1 0.007 0.001% 99.999% 0.000 CAST 1 0.002 0.000% 100.000% 0.000 1 Subtract (ND, F32) 1 0.001 0.000% 100.000% 0.000 1 Multiply (ND, F32) 1 0.001 0.000% 100.000% 0.000 1在OP Profile报告中，被托管到NNAPI上运行的子图会以TfLiteNnapiDelegate的形式显示，无法追踪算子的具体信息，所以我们只需要关心那些被具体列出的算子（这些算子证明无法在NNAPI上运行）即可。但是注意由于我们之前提到的子图尽可能大原则，因此这些列出的算子不一定全都是完全不能运行的算子，我们只关注占比较多的部分即可。令我很诧异的是，不能运行的算子中更多竟然是很基础的FullyConnected层算子，因此这个问题似乎不仅仅是算子不支持那么简单。从头开始分析，一个TensorFlow中计算首先会被编译为图算子(tf.op)，此后在TensorFlow Lite的转化过程中会被转化为TFLite支持的算子(如上文提到的Matmul转为FC)并将结构连同Weighs一同固化在TFLite文件中，再在TFLite Lib运行时转换为NNAPI的抽象OP算子。如果一个看上去很简单的算子无法完成这个流程，那很可能是某个转化过程出了问题，导致最终生成的NNAPI算子被拒绝了。首先我决定还是利用可视化工具看看TFLite中的算子类型有没有奇怪之处，通用的可视化工具如[Netron]可以显示模型结构，但是不一定可以展示TFLite的私有信息，这里我们使用TFLite自带的可视化工具，如果你已经安装了TF，直接在终端运行：python -m tensorflow.lite.tools.visualize <TFLite 文件路径> <生成报告HTML文件路径>很遗憾，我这里生成的报告非常庞大（毕竟模型结构比较深）且没啥实用信息。这条路好像不太能走通，我决定还是去翻下子图分派的代码，看看这个OP为什么会被NNAPI拒绝。好在虽然TensorFlow的仓库很庞大，但还算得上有条理。在https://github.com/tensorflow/tensorflow/blob/master/tensorflow/lite/delegates/nnapi/nnapi_delegate.cc 中找到了较为详细的逻辑。// Return a function that knows how to translate a node into its operands // when called. You can use this function to see if a node is supported // (i.e. if the returned MappingFn is null, then the node is not supported). bool NNAPIDelegateKernel::Validate( const TfLiteContext* context, const TfLiteRegistration* registration, int android_sdk_version, const TfLiteNode* node, bool is_accelerator_specified, NnapiDelegateVendorPlugin* vendor_plugin, std::vector<NNAPIValidationFailure>* map_failures) { ... case kTfLiteBuiltinFullyConnected: { ExpectMaxOpVersion(version, 5, &val_ctx); const auto output_type = context->tensors[node->outputs->data[0]].type; Expect(output_type != kTfLiteInt16, NNAPIValidationFailureType::kUnsupportedOutputType, "Unsupported output of type kTfLiteInt16", &val_ctx); if (android_sdk_version < kMinSdkVersionForNNAPI12) { Expect(!IsHybridOperator(context, builtin_code, node), NNAPIValidationFailureType::kUnsupportedHybridOperator, "Hybrid operators not supported before NNAPI 1.2", &val_ctx); ExpectIsFloatOrUint8Operator(context, node, &val_ctx); } const auto input_type = context->tensors[node->inputs->data[0]].type; if (android_sdk_version < kMinSdkVersionForNNAPI12 && input_type == kTfLiteUInt8) { ExpectIsRestrictedScalesCompliant(context, node, &val_ctx); } auto builtin = reinterpret_cast<TfLiteFullyConnectedParams*>(node->builtin_data); if (builtin->keep_num_dims) { ExpectMinAndroidSdkVersion(android_sdk_version, kMinSdkVersionForNNAPI13, &val_ctx); } } break; ... }TFLite通过Validate函数来确定某个node能不能在指定后端上运行，如果能运行则返回在后端上的实现Operand(即操作数，负责承载Model中的数据流向或常量，用作Operation的输入与输出)，否则返回null.走读下代码，发现代码中依次判断了是否为INT16输出(肯定没有)以及某些特性是否支持（这可能是一个错误点，但是我手上的这台最新款Pixel已经升级到最新版本的Android13 with PixelFeatureDrop，NNAPI也是最新的1.3版本，也应当不会出现问题）。正当我疑惑时，才发现最开始的ExpectMaxOpVersion(version, 5, &val_ctx)调用断言了算子版本，而从上文中的可视化界面可知，生成的FullyConnected算子的Version竟然高达9！原来，可能是FullyConnected算子引入了什么新特性，而NNAPI Adaptor没有跟进，只是把含有这些新特性的算子全部拒绝了。那么我们只想要去除这些新特性就可以了。再来看看TensorFlowLite转换器的代码，看看是什么导致了版本号狂飙猛进:// https://github.com/tensorflow/tensorflow/blob/master/tensorflow/lite/tools/versioning/op_version.cc int GetBuiltinOperatorVersion(const OpSignature& op_sig) { switch (op_sig.op) { ... case BuiltinOperator_FULLY_CONNECTED: { // +-----------------+--------------------+--------------------------+ // | | Weight::Default | Weight::Shuffled4x16Int8 | // +-----------------+--------------------+--------------------------+ // | Float | 1 | 2 | // | Quantized Uint8 | 1 | 2 | // | Hybrid | 3 | 3 | // | Quantized Int8 | 4 | 4 | // +-----------------+--------------------+--------------------------+ // FullyConnected with sparse weight is supported at version 8. if (op_sig.ext_options.fully_connected.sparse_weight) { return 8; } // Int16 fully fixed point kernel is at version 7. if (op_sig.inputs.at(0).type == kTfLiteInt16 && op_sig.inputs.at(1).type == kTfLiteInt16 && op_sig.outputs.at(0).type == kTfLiteInt16) { return 7; } // 2 op_sig.inputs (no bias) use case is supported starting from // version 6. if (op_sig.inputs.size() == 2) { return 6; } auto fully_connected_params = reinterpret_cast<TfLiteFullyConnectedParams*>(op_sig.builtin_data); TFLITE_DCHECK(fully_connected_params != nullptr); // `keep_num_dims` is supported at version 5. if (fully_connected_params->keep_num_dims) { return 5; } // Int8 fully fixed point kernel is at version 4. if (op_sig.inputs.at(0).type == kTfLiteInt8 && op_sig.inputs.at(1).type == kTfLiteInt8 && op_sig.outputs.at(0).type == kTfLiteInt8) { return 4; } // If the op has signed int8 and int4 op_sig.inputs and op_sig.outputs, // its version 7. if (op_sig.inputs.at(0).type == kTfLiteInt8 && op_sig.inputs.at(1).type == kTfLiteInt4 && op_sig.outputs.at(0).type == kTfLiteInt8) { return 10; } // If the op is a signed int8 hybrid operation, we need to return // version 3. if (op_sig.inputs.at(0).type == kTfLiteFloat32 && op_sig.inputs.at(1).type == kTfLiteInt8 && op_sig.outputs.at(0).type == kTfLiteFloat32) { if (fully_connected_params->asymmetric_quantize_inputs) { // This is to use the updated quantization scheme. return 9; } return 3; } // For float and uint8 fixed point kernels, if the weight is // Shuffled4x16Int8, it is version 2. if (fully_connected_params->weights_format == kTfLiteFullyConnectedWeightsFormatShuffled4x16Int8) { return 2; } // Otherwise (weight is default), the version is 1. return 1; } }看来与模型的算子特性无关，新版本更多是与量化有关系，引入了非对称量化、稀疏weight等特性。然而在转化模型的时候并没有转化量化模型啊？再次以asymmetric_quantize_inputs为关键字在代码库中查询，从MLIR的一条注释得知，当在convertor中指定converter.optimizations = [tf.lite.Optimize.DEFAULT] 时，默认就会包含这个优化策略，并导致OP Version飙升。只能说难绷…理论上也可以通过魔改MLIR的相关代码关闭这个策略，但是我还是选择了直接关闭了转换优化，效果如下，大部分算子都成功调度到NNAPI上:VERBOSE: Replacing 3174 out of 3219 node(s) with delegate (TfLiteNnapiDelegate) node, yielding 26 partitions for the whole graph.一朵乌云然而真正运行时却直接抛出错误: NN API returned error ANEURALNETWORKS_OP_FAILED at line 4735 while completing NNAPI compilation.这下毫无疑问是NNAPI的锅了。查询文档发现 幸好NNAPI留出了一个日志选项，允许我们获取运行时的相关Logs并在logcat中查看:adb shell setprop debug.nn.vlog all最终发现问题出在设备供应商提供的HAL层，报错信息也十分奇诡:On fd 14, read operation attempted on 40 bytes, but zero bytes affected. (This could be due to reading past EOF). Context: /data/vendor/hal_neuralnetworks_darwinn/NnapiHalSocketSpawnerProcess 这FD打不开算个什么事情！查报错信息未果，HAL的代码肯定也是完全不可见的。在排除了文件损坏之后，我突然想到，在Linux编程中，Hardware Buffer或者MMAP这些东西似乎也经常使用read调用读取，会不会是某个Buffer/内存不足了呢？尝试减小模型推理时的BatchSize，将BatchSize砍半之后成功运行。Latency: 38ms ✅后记26个Part还是有点多..能不能再少一点? 仔细看下就会发现 现在影响Part数量的估计是MEAN算子(OP表里说它26个,数字是不是很相近?) MEAN算子也是个常用算子了,为啥会不能跑捏? 这个问题也困惑了我很久,目前发现的结论是 TF的ReduceMean OP单独使用是没有问题的,但是假如在ReduceMean函数中axis参数传入一个数组(一个以上数字) 很可能没办法跑, 而Bert结构中的moments OP更是会出现奇怪的Bug(当axis是1时可以跑,axis>1(比如2)或数组,不能跑).诡异到这种地步,不太想继续往下追了 就这样吧.
背景出于菜鸡的摸鱼需求，希望用插件的形式为Github增加用户备注标签功能，大概的设计如下：浏览器插件注入ContentScript修改页面内容，增加标签显示和相关操作按钮利用浏览器提供的Sync Storage功能在多设备同步标签数据经过一天的摸鱼，插件功能已经基本完成:But…跨设备同步功能却出现了问题:对于未上架Chrome Store的拓展而言，拓展的ID安装时生成的，且在不同设备上安装时不一定一致。而Chrome提供给拓展 Sync Storage功能是与ID相绑定的，因此无法完成不同设备上的同步功能。Extension Key的生成在谷歌官方的文档里，我找到了Key 这个Manifest键值，但是官方要求必须在Developer Dashboard才能生成这个公钥属性。随后我发现，谷歌浏览器的开发者需要5刀乐注册费…还不支持银联卡。随手填了个Key值，加载报错Invalid.穷鬼如我决定去翻下Chromium的相关代码，看看PublicKey到底是怎么验证的。好在Chromium的代码仓库很条理，还带有搜索功能，很快就找到了相关代码段：//extensions/common/extension.cc // Computes the |extension_id| from the given parameters. On success, returns // true. On failure, populates |error| and returns false. bool ComputeExtensionID(const base::Value::Dict& manifest, const base::FilePath& path, int creation_flags, std::u16string* error, ExtensionId* extension_id) { if (const base::Value* public_key = manifest.Find(keys::kPublicKey)) { std::string public_key_bytes; if (!public_key->is_string() || !Extension::ParsePEMKeyBytes(public_key->GetString(), &public_key_bytes)) { *error = errors::kInvalidKey; return false; } *extension_id = crx_file::id_util::GenerateId(public_key_bytes); return true; } if (creation_flags & Extension::REQUIRE_KEY) { *error = errors::kInvalidKey; return false; } // If there is a path, we generate the ID from it. This is useful for // development mode, because it keeps the ID stable across restarts and // reloading the extension. *extension_id = crx_file::id_util::GenerateIdForPath(path); if (extension_id->empty()) { NOTREACHED() << "Could not create ID from path."; return false; } return true; } bool Extension::ParsePEMKeyBytes(const std::string& input, std::string* output) { DCHECK(output); if (!output) return false; if (input.length() == 0) return false; std::string working = input; if (base::StartsWith(working, kKeyBeginHeaderMarker, base::CompareCase::SENSITIVE)) { working = base::CollapseWhitespaceASCII(working, true); size_t header_pos = working.find(kKeyInfoEndMarker, sizeof(kKeyBeginHeaderMarker) - 1); if (header_pos == std::string::npos) return false; size_t start_pos = header_pos + sizeof(kKeyInfoEndMarker) - 1; size_t end_pos = working.rfind(kKeyBeginFooterMarker); if (end_pos == std::string::npos) return false; if (start_pos >= end_pos) return false; working = working.substr(start_pos, end_pos - start_pos); if (working.length() == 0) return false; } return base::Base64Decode(working, output); }从相关代码段可以看出，ID的生成有两种来源，一种来自于拓展存放的路径(Path)，其实就是把Path字符串做哈希之后生成ID，另一种就是来着于Key字段，通过ParsePEMKeyBytes进行校验，而校验的逻辑仅仅是简单的Base64Encode(难绷…)随便在Key字段中填写了一段Base64编码(如SUFtQUxvbmVseUhlbGljb3B0ZXI=),成功导入，且ID固定不再变更，收工！另,上文提到的浏览器拓展开源在这里(尚未完工)
前言TailScale是一个很优秀的组网服务，特别适合拓展家里的局域网，让你在外面也可以访问家中的内网设备。基于WG 的底层设计也使得TailScale有更好的性能和安全性，但是TailScale的工作机制是先使用Relay节点(Derper)建立连接，再尝试进行打洞直连。由于我国特殊国情，一方面IPv4大部分处于NAT之后，导致连接大部分依赖Derper中转，另一方面Derper并没有国内的节点，导致连接的延迟很高。好在TailScale提供了一个Alpha版本的自建Derper指南(链接)，但是要求必须开放443端口，对国内的VPS很不友好。但是经过测试与审阅源码，发现443并非必须，且仍可以利用客户端验证设备。要求如下：需要域名绑定IP需要HTTPS证书（如果自签证书，要保证连接到VPS的节点均信任此证书）开放端口（不必须443）搭建方法安装最新版Go(版本至少要1.16以上才能执行go install +url@version 命令,且Derper的代码只在最新版Golang下测试)直接按照官方版指南安装官方最新版本Derper为自己的域名签发HTTPS证书，需要 hostname.crt 与hostname.key 保存在同一目录使用下面的语句执行启动Derper命令:sudo derper --a :10080 --http-port -1 --certmode manual --certdir ./certDir --hostname HOSTNAME --verify-clients # 假设SSL端口为10080 关闭http-port（-1) 将证书模式设置为手动(非443不可自动获取证书) # 指定证书的目录在certDir下,指定域名为 HOSTNAME，并开启客户端验证最后记得加入本Derper节点到各客户端配置文件，如果使用官方版本，在Admin Console的ACL部分编辑即可，同步到各个节点可能要花费一部分时间。客户端验证在开启Derper的命令中加入 —verify-clients Flag可开启客户端验证功能，开启后只有账号下的设备可以接入本DERP。开启此功能的要求是：必须有域名和证书绑定Derper节点也要运行TailScale并登录账号，接入用户的校验是通过调用本机的TailScale应用暴露的API来完成的。