Posts

CMOS MOSFET Overview Characters Two Flavors CMOS CMOS is Complementary Metal Oxide Semiconductor Two switches Inverter Basic usage of CMOS Timing specifications Propagation Delay Contamination Delay Summary

上官体 上官仪 背景 上官仪是初唐文学的重要人物，开创了上官体，特点是绮错婉媚，上承虞世南，下启沈佺期和宋之问。不过后来被杨炯批评为有风韵，但无风骨。 代表作 咏画障 芳晨丽日桃花浦，珠帘翠帐凤凰楼。 蔡女菱歌移锦缆，燕姬春望上琼钩。 新妆漏影浮轻扇，冶袖飘香入浅流。 未减行雨荆台下，自比凌波洛浦游。 新装漏影浮新扇，冶袖飘香入浅流。 未减行云荆台下，自比凌波洛浦游。

The Digital Abstraction 信息编码 信息的种类有各种各样，我们需要找到一种方式来表示这些信息。比如，生物的基因信息是通过DNA来记录和表达，在计算机中，所有的数据都是二进制，我们也需要一个物理介质来表达和存储这些二进制信息。 电压 目前用来存储和表达二进制信息的物理介质绝大部分都是使用电压，高电平表示1, 低电平表示0。 VTC和容错 VTC(voltage transfer characteristics)是用来表示一个电子原件的输入和输出电压关系的图，如下是一个Buffer的VTC： 其中$V_{IL},V_{IH},V_{OL},V_{OH}$是一个电子元件最重要的参数，解释如下（这里假设最高电压为1）： $V_{IL}$是低电平的输入有效范围，即如果输入电压为$[0,V_{IL}]$，就会被元件当成0处理。 $V_{IH}$是高电平的输入有效范围，即如果输入电压为$[V_{IH}, 1]$，就会被元件当成1处理。 $V_{OL}$是低电平的输出电压，即如果元件想输出0，则其输出电压应该为$[0, V_{OL}]$。 $V_{OH}$是高电平的输出电压，即如果元件想输出1，则其输出电压应该为$[V_{OH},1]$。 其中, $min(|V_{OL} - V_{IL}|, |V_{OH} - V_{IH}|)$即为该元件能容忍的噪声范围。 Summary

Basic of Information 信息是什么 信息是我们接收到的关于确实某个特定事件或者情况的数据。 量化信息 对于随机变量$X_i$，其发生的概率为$p_i$，则其传达的信息量为: $$I(x_i) = \log_2(\frac{1}{p_i})$$ 数据中的信息 假设收到data的概率$p_{data}$，则 $$I(data) = \log_2(\frac{1}{p_{data}})$$ Entropy 信息论中的entropy： $$H(X) = \sum_{i=1}^{N}p_i\log_2(\frac{1}{p_i})$$ 其中$X$为随机变量。 物理中的entropy： $$ S = k\ln\Omega $$ 其中，$k$为玻尔兹曼常数 Meaning of Entropy 为了描述某一个随机变量$X$，需要传输一系列的数据，Entropy就是确定$X_i$发生与否的平均位数，即传输量。 编码 编码就是把一个数据集合映射为一系列二进制字符串。常见的编码是把英文字母用二进制来表示，比如如下表格： A B C D ABBC的编码 00 01 10 11 00 01 01 00 01 1 000 001 01 1 1 01 0 1 10 11 0 1 1 0（无法确定） 编码不能有二义性 二叉树编码 用二叉树的边当作0和1,叶子节点当作编码的值，可以去除二义性。 定长编码 所有值的编码长度都相等。 2的补码 即将二进制最高位的全值定为$-2^{N-1}$ ...

Introduction to basic conception The Continuum of Numbers 首先，自然数可以认为是与生俱来的，但是普通的四则运算所产生的结果却不一定是自然运算，比如$1 - 1 = 0$ , $1 - 2 = -1$ , $1\div2 =\frac{1}{2}$都产生了结果不是自然数的情况。为了满足四则运算能更方便的使用，便引入了$0$ 、分数和负数，即有理数。 有理数的引入使得四则运算的适用范围更广，但有理数是否就能表示生活中所有能见到的物体的度量呢？答案是否定的，比如两个直角边都为1的直角三角形，根据毕达哥拉斯定理，其斜边的平方为$c^2 = 1^2 + 1^2$，但我们无法找到一个有理数，使得其平方为$2$，所以，有理数并不能满足所有的计算。 Real Number and Nested Interval 现在我们用数轴上的点来当作Continuum of Numbers的基本元素，其中每个点都对应一个实数x, 实数之间的大小关系就是其在数轴上的位置关系，比如x在y左边则$x < y$. 我们已经知道有理数可以用两个整数p和q的商$\frac{p}{q}$来定义，那该如何用已知的有理数或者自然数来定义无理数呢？数学中常用的一种做法是渐进，即找一个无限接近目标的序列，其项数越多，误差就越小。为了取得无理数x的渐进值，我们需要从两边同时靠近它(只考虑一边的话便没有终止条件)，即在其他左右两边各取一个有理数，比如$a_1$和$b_1$, 且$a_1 < x$,$b_1 > x$, 这样，就选取了一个包含x的区间$[a_1, b_1]$。然后，将$[a_1, b_1]$对半分，取其中包含x的区间$[a_2, b_2]$，则$a_1 \le a_2 < x$, $x < b_2 \le b_1$。同样的，我们可以继续二分$[a_2, b_2]$，并不断重复下去，则可以得到任意个包含x的区间，且$[a_n, b_n]$包含于$[a_{n+1}, b_{n+1}]$，我们称这样一个区间序列为嵌套区间 。很显然，每个区间与x的误差不超过$|b_n - a_n|$。 小数 在前面的嵌套区间中，$a_n < x < b_n$。现在将数轴按以1为单位标记，然后将每个单位长度区间10等分。假设$0 \le x \le 1$，且x肯定在$[0, 1]$区间10等分后的某个小区间中，假设为$[\frac{a_1}{10},\frac{b_1}{10}]$，则$\frac{a_1}{10} \le x \le \frac{b_1}{10}$。接下来将$[\frac{a_1}{10}, \frac{b_1}{10}]$继续10等分，则会有 ...

算法 什么是算法 形式上的定义 Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. 个人理解 算法是CS中很多技术的基础，也应该是CS的核心所在。 排序问题 插入排序 插入排序的过程跟打扑克时起牌的过程差不多，对于位置i的元素，在其前面找到应该插入的位置插入即可，复杂度是$\theta(n^2)$。 归并排序 归并排序就是将原序列递归分成多个小序列，然后合并的时候发现每个元素只需要$O(1)$的时间就可以确定其位置，比较次数较插入排序少了很多，所以复杂度比插入排序小，为$\theta(nlogn)$。 归并+插入 考虑到算法复杂度的常数，在数据规模较小时，插入排序可能会比归并更优，所以在归并排序中，当子序列规模小于k时，可采用插入排序来完成。 延伸问题 逆序对 序列中，数值和位置的大小关系不匹配便可以称为一个逆序。思考一下，可以发现插入排序中，元素的比较次数就是序列中逆序对的个数，而归并排序中同样也能推算出所有的比较次数，故可以在$\theta(nlogn)$的复杂度下解决该问题。

Introduction paper url: http://nil.csail.mit.edu/6.824/2020/papers/mapreduce.pdf Why need distributed parallelism fault tolerance physical security or isolated Basic challenges concurrency partial failture performence Map Reduce 个人理解 MapReduce是一个比较直观而且可以分布式的编程框架，主要过程就是将数据（输入）分发到不同的task（map过程），然后将所有task的输出收集起来shuffle一下，然后分发给另外的task（reduce过程）。从目前（2021年）来看，这个编程模型的瓶颈应该是中间的shuffle过程，因为数据量非常大的时候，shuffle过程的网络IO量也非常大。 关键点 MapReduce的编程模型很简单，但Google的论文中最有价值的部分是应该是关于容错和任务备份。 容错 Worker容错 每个Task可以分为三个状态，idle/in-progress/completed，当task被分配给worker后，会由idle变为in-progress状态，当worker正常完成task时，会由in-progress变为completed。 当worker因意外或其他原因变得inavaible时，Task将会变成idle状态，然后master就可以将其重新分配给其他worker去完成。 Master容错 Master的错误比较暴力，直接做几个mirror就行了，如果没有mirror，那么当master出错时，整个系统就会宕机。 任务备份 个人觉得是论文里一个不错的点，任务备份是当一个MapReduce操作（个人理解就是map和reduce)完成时，将当前in-progress的Task备份，然后当有空闲的worker时再将备份中的task分配过去执行。这样的好处是可以明显减少因为straggler的存在而导致的性能下降。 straggler指因为磁盘、网络等原因而造成性能下降的Worker personal idea 因为在实际情况中，每个Worker都会因为各种因素而产生性能上的差距。同时，Master中也记录了每个task的完成时间，感觉可以用完成时间的平均值（或者之类的）来将worker放到一颗平衡树里面，然后优先用效率高的worker去完成task。

My Archlinux desktop configuratoins Basic setup Desktop Environment KDE Bismuth Fonts Apple Developer fonts Wenquanyi Sarasa FiraCode Nerd mono App icons Tela Dotfiles Apply dotfiles from my own repo Softwares for daily use qView: image viewer thunar: graphical file manager ranger: console file manager Typora: writing articles Thunderbird: mail and rss client Yesplaymusic: music player Zotero: PDF/paper read and management

数电设计和计算机结构：从0到1（第一章） 计算机的抽象结构 Application Software: Programs Operating Systems: Device Drivers Architecture: Instructions Registers Microarchitecture: Datapaths Controllers Logic: Adders Memories Digital Circuits: AND Gates/NOT Gates Analog Circuits: Amplifiers Filters Devices: Transistors Diodes Physics: Electrons 二进制 信息量 N种状态需要$ log_2{N} $个Bit 补码 我们一般学习补码都是分正数和负数，正数不变，负数将对应的绝对值按位取反再加1。不过在这本书中学到了一个新的角度：将MSB(二进制最高位)的全值当成$ -2^{N-1}$即可，这样看补码的话也更直观一些。 逻辑门 基本的一些门电路 AND OR NOT NAND XOR NOR Buffer Logical level 数字电路处理的是离散量，比如电压只有高电平和低电平（一般用1和0表示），但实际上电路中的电压是连续变化的，那么怎么把连续的量转化为离散的量呢？ 逻辑门的输入输出电压 逻辑门的输入输出中，所用的高电平和低电平的范围可能会不相同。对于输出，高电平一般是在$V_{OH} - V_{DD}$之间，而低电平是在$GND - V_{OL}$之间。而当门电路读取输入时，低电平一般是在$GND-V_{IL}$之间，高电平是在$V_{IH} - V_{DD}$之间，这样的话，在一套逻辑电路内，必须要有: $$ V_{OL} \leq V_{IL} $$ $$ V_{OH} \leq V_{IH} $$ ...

Linux日常使用 应用推荐 阅读+笔记 Masterpdfeditor 全平台的PDF编辑器，日常阅读+标注可以满足需求，完整版需付费。 XMind 思维导图软件，全平台，简单好用。 Zotero 文献管理软件，配合zotfile和云盘可以实现多端同步。 云同步 Google Drive 某知名网盘。 Insync Google Drive和Onedrive的客户端，全平台，授权费30刀（终身），还算好用。 开发 IDE Jetbrains JB全家桶，全平台。 Neovim 用neovim开发也是个不错的选择，配合coc和其他自己喜欢的插件，也有不错的体验，而且资源消耗比JB之类的IDE少很多。 浏览器 Chromium 日常使用和Chrome的差别感觉不是很大，也可以同步Google帐号的数据。 杂项 Thunderbird 邮件客户端 + RSS客户端，免费好用。 KeepassXC 密码管理器kepass的一个GUI前端，免费，界面也还不错，全平台。 Typora Markdown写作软件，用来写博客非常不错，免费全平台。 Goldendict 字典软件，免费全平台，很方便，字典需另外需找，目前使用的是： 牛津10 新世纪日汉双解大辞典(精)