KylinChen | Blog

S3 Scheduling with predictable decoding

Increasing GPU Utilization during Generative Inference for Higher Throughput

[TOC] Abs challenge: KV cache内存消耗大，现有方法保留max length的KV cache => 导致 bs 小 => GPU利用率不高 insight: 预测output length，并根据这个predictions进行scheduling Intro 这个图说明的是throughput和latency的权衡，虽然我们希望通过牺牲l...

Posted by Kylin on January 7, 2024

理解辗转相除法

gcd原理解析

[TOC] 辗转相除法1 辗转相除法是用来求 greatest common divisor(GCD) 的算法。 def gcd(a:int,b:int)->int: if not b: return a else: return gcd(b,a%b) 原理解析2 对于任何可以整除a和b的整数，那么它也一定能整除a-b（和b)，因此我们选择该整数（...

Posted by Kylin on January 6, 2024

Deja Vu

Contextual Sparsity for Efficient LLMs at Inference Time

[TOC] Abs 主要关注的是inference时候的computationally expensive 以往搞sparse的有两个问题：忽略LLM的in-context learning能力，要retrain一下不能再hardware上实现wall-clock time speedup 介绍了一个新概念：Contextual Sparsity：small, in...

Posted by Kylin on January 5, 2024

PowerInfer

Fast Large Language Model Serving with a Consumer-grade GPU

[TOC] Abs Objective: PowerInfer is introduced as a high-speed LLM inference engine optimized for personal computers equipped with a single consumer-grade GPU. Insight： minority, hot neurons: co...

Posted by Kylin on January 4, 2024

Gosper's Hack

Gosper's Hack原理解析

[TOC] Gosper’s Hack1 Gosper‘s Hack用来逐一生成二进制枚举中n位含有k位1的二进制数。 def GospersHack(k:int,n:int)->None: cur = (1<<k)-1 limit = (1<<n) while cur<limit: lb = cur&-cu...

Posted by Kylin on January 4, 2024

Towards Efficient Generative Large Language Model Serving A Survey from Algorithms to Systems

高效LLM推理算法&系统综述

[TOC] https://arxiv.org/abs/2312.15234 Challenge LLM deployment: computational intensity, memory consumption 两个需求都很大 => 减少需求（量化、稀疏剪枝）考虑到具体硬件设备上，两个需求不平衡（调度，任务划分） serving scenarios...

Posted by Kylin on January 3, 2024

Coding on 中位数贪心

中位数贪心及题单

[TOC] 中位数贪心一个简单的问题：我们有一个数组a，我们要找一个数x，使得数组a中的每一个数到x的绝对距离之和最小，那么这个数是多少？定理: 将 $a$ 的所有元素变为 $a$ 的中位数是最优的。证明: 设 $a$ 的长度为 $n$ ，设要将所有 $a[i]$ 变为 $x$ 。假设 $a$ 已经从小到大排序。首先，如果 $x$ 取在区间 $[a[0], a[n-1]]$ 之外...

Posted by Kylin on December 17, 2023

红黑树最大高度

红黑树最大树高的更准确估计

[TOC] Definition 这里红黑树相关定义沿用的是邓公版数据结构中的定义：树高：从根节点到叶节点路径长（空树树高-1，单节点树树高0）红黑树树高：从根节点到外部节点的路径长 Proof 查阅了一圈网上的资料，发现对于红黑树树高的证明只有一个相对较宽松的上界：设内部节点为n，外部节点为n+1，那么黑高度 bh 满足 bh&...

Posted by Kylin on December 14, 2023

Coding on 二维前缀和(差分)

二维前缀和(差分)及题单

[TOC] 差分数组举例考虑数组 $a=[1,3,3,5,8]$ ，对其中的相邻元素两两作差（右边减左边），得到数组 $[2,0,2,3]$ 。然后在开头补上 $a[0]$ ，得到差分数组 \[d=[1,2,0,2,3]\] 这有什么用呢? 如果从左到右累加 $d$ 中的元素，我们就「还原」回了 $a$ 数组 $[1,3,3,5,8]$ 。这类似求导与积分的概念。这又有什么...