AMBA总线(6)—— C-channel、Q-channel、P-channel
AMBA总线(5)—— AXI5新feature
前面博客《AMBA总线(3)—— AXI协议》大致过了一遍 AXI3 和 AXI4 协议,对于 AXI5 部分没有研究。本篇博客翻译一下 AXI5 中的新 feature,参考文档是《AMBA5 AXI and ACE Protocol Specification》。


AMBA总线(3)—— AXI协议
AMBA总线(2)—— AHB协议
AMBA总线(1)—— APB协议
APB是最简单的AMBA总线了,功耗很低,它多用于低速外围设备和访问寄存器。相比AHB和AXI,有几个很不一样的点:
- 最快只能背靠背(back to back)传输,至少2个周期传输一个数据,PSEL起来然后PENABLE起来。
- 背靠背传输,即连续传输,这笔传输传完,紧挨着下一个Cycle就可以开始下一笔传输。
- 不能Pipeline传输、Burst传输、Outstanding传输,数据有效时,其地址必然是当前数据的对应地址。
- pipeline传输,即流水式传输,指当前传输的结束Cycle可以是下一笔传输的起始Cycle,起到无缝衔接。
- burst传输,即只需指定起始地址和突发长度,即可自动对后面连续地址进行操作,无需提供连续地址。
- outstanding传输,即不需要等待读写数据完成,即可继续提供下一笔传输的命令和地址,提高传输效率。
- 不能读写同时传输,因为其读写地址是共用的。(AHB也不能读写同时传输)
- 不能仲裁,因为是单主多从协议。典型的APB协议包括唯一的APB桥作为Master,而所有的APB模块都是APB slave。

AMBA总线(0)—— 学习导论
ARM 公司推出了 AMBA 系列总线,一直迭代至今,不断丰富扩展内容,常用的 AMBA 协议各个版本的变化如下所示:

在我刚入职时,指导人让我前 2 个星期什么都不用干,甚至不用登陆 Linux 系统,就在电脑上硬看 APB、AHB、AXI 数据手册。那时我连基本的握手、互联的概念都没有,看完后虽有收获,但非常流于表面。现在工作了一小段时间,打算再看一遍 AMBA 数据手册,希望把边边角角都给扫到。
十大排序算法
算法分类
十种常见排序算法可以分为两大类:
比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。
非比较类排序:不通过比较来决定元素间的相对次序,它可以突破基于比较排序的时间下界,以线性时间运行,因此也称为线性时间非比较类排序。

时间,空间复杂度比较
| 排序算法 | 英文 | 平均时间复杂度 | 最差时间复杂度 | 空间复杂度 | 数据对象稳定性 | |
|---|---|---|---|---|---|---|
| 选择排序 | selection | O(n2) | O(n2) | O(1) | 数组不稳定、链表稳定 | |
| 冒泡排序 | Bubble | O(n2) | O(n2) | O(1) | 稳定 | |
| ★ | 插入排序 | insertion | O(n2) | O(n2) | O(1) | 稳定 |
| ★ | 快速排序 | Quick | O(n*log2n) | O(n2) | O(log2n) | 不稳定 |
| ★ | 归并排序 | Merge | O(n*log2n) | O(n*log2n) | O(n) | 稳定 |
| ★ | 堆排序 | heap | O(n*log2n) | O(n*log2n) | O(1) | 不稳定 |
| 希尔排序 | shell | n^1.3 | O(n2) | O(1) | 不稳定 | |
| 桶排序 | Bucket | O(n) | O(n) | O(m) | 稳定 | |
| 计数排序 | Counting | O(n+m) | O(n+m) | O(n+m) | 稳定 | |
| 基数排序 | Radix | O(k*n) | O(n2) | O(n+k) | 稳定 |
