用并行技术但是并行时我们要考虑必须串行执行的任务也就是有依赖关系的任务任务中的重点往往是具体的数据这些任务中的数据通常具有局部性和关联性。

而数据中数组具有代表性现在让笔者从数组开始谈谈程序数据的优化。

ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-EMPvLuYQyarcCgR4

.error-icon{fill:#552222;}#mermaid-svg-EMPvLuYQyarcCgR4

.error-text{fill:#552222;stroke:#552222;}#mermaid-svg-EMPvLuYQyarcCgR4

.edge-thickness-normal{stroke-width:2px;}#mermaid-svg-EMPvLuYQyarcCgR4

.edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-EMPvLuYQyarcCgR4

.edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-EMPvLuYQyarcCgR4

.edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-EMPvLuYQyarcCgR4

.edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-EMPvLuYQyarcCgR4

.marker{fill:#333333;stroke:#333333;}#mermaid-svg-EMPvLuYQyarcCgR4

.marker.cross{stroke:#333333;}#mermaid-svg-EMPvLuYQyarcCgR4

ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-EMPvLuYQyarcCgR4

ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-EMPvLuYQyarcCgR4

.cluster-label

text{fill:#333;}#mermaid-svg-EMPvLuYQyarcCgR4

.cluster-label

span{color:#333;}#mermaid-svg-EMPvLuYQyarcCgR4

.label

text,#mermaid-svg-EMPvLuYQyarcCgR4

span{fill:#333;color:#333;}#mermaid-svg-EMPvLuYQyarcCgR4

.node

rect,#mermaid-svg-EMPvLuYQyarcCgR4

.node

circle,#mermaid-svg-EMPvLuYQyarcCgR4

.node

ellipse,#mermaid-svg-EMPvLuYQyarcCgR4

.node

polygon,#mermaid-svg-EMPvLuYQyarcCgR4

.node

path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-EMPvLuYQyarcCgR4

.node

.label{text-align:center;}#mermaid-svg-EMPvLuYQyarcCgR4

.node.clickable{cursor:pointer;}#mermaid-svg-EMPvLuYQyarcCgR4

.arrowheadPath{fill:#333333;}#mermaid-svg-EMPvLuYQyarcCgR4

.edgePath

.path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-EMPvLuYQyarcCgR4

.flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-EMPvLuYQyarcCgR4

.edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-EMPvLuYQyarcCgR4

.edgeLabel

rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-EMPvLuYQyarcCgR4

.cluster

rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-EMPvLuYQyarcCgR4

.cluster

text{fill:#333;}#mermaid-svg-EMPvLuYQyarcCgR4

.cluster

span{color:#333;}#mermaid-svg-EMPvLuYQyarcCgR4

div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet

ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80,

100%,

#aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-EMPvLuYQyarcCgR4

:root{--mermaid-font-family:"trebuchet

处理器

ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.error-icon{fill:#552222;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.error-text{fill:#552222;stroke:#552222;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.edge-thickness-normal{stroke-width:2px;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.marker{fill:#333333;stroke:#333333;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.marker.cross{stroke:#333333;}#mermaid-svg-RJXE9Vbu9Vay5WGi

ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-RJXE9Vbu9Vay5WGi

ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.cluster-label

text{fill:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.cluster-label

span{color:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.label

text,#mermaid-svg-RJXE9Vbu9Vay5WGi

span{fill:#333;color:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.node

rect,#mermaid-svg-RJXE9Vbu9Vay5WGi

.node

circle,#mermaid-svg-RJXE9Vbu9Vay5WGi

.node

ellipse,#mermaid-svg-RJXE9Vbu9Vay5WGi

.node

polygon,#mermaid-svg-RJXE9Vbu9Vay5WGi

.node

path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.node

.label{text-align:center;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.node.clickable{cursor:pointer;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.arrowheadPath{fill:#333333;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.edgePath

.path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.edgeLabel

rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.cluster

rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.cluster

text{fill:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi

.cluster

span{color:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi

div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet

ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80,

100%,

#aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-RJXE9Vbu9Vay5WGi

:root{--mermaid-font-family:"trebuchet

速度从慢到快

虚拟内存是一个很伟大的发明它借助内存管理单元MMU并利用分页机制将磁盘的一部分模拟为内存使用。

它允许计算机使用硬盘空间来扩展实际的物理内存。

这使得操作系统能够运行超过实际物理内存容量的程序。

cache命中率

cache会从更低一级的内存结构中搬数据如果数据访问是局部性很强如访问同一数据块多次则缓存命中率会较高如果不命中那么计算机会跑到下一级内存中寻找数据这样程序运行效率就会非常低。

for(int

}在C语言中二维数组的内存分布通常是按行优先Row-major

order存储的这意味着数组的行是连续存储在内存中的。

具体来说对于一个二维数组

假设我们有一个二维数组

Z[m-1][n-1]每一行的元素是连续存储的然后依次存储下一行的元素。

for

┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐

0,0

└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

┌─────┬─────┬─────┬─────┬─────┬─────

0,0

└─────┴─────┴─────┴─────┴─────┴─────

局部性更好的程序如下此时想要一眼看出来这样写就有点困难了那我们要怎么推导数组的遍历式呢

for

现在我们得到了矩阵我们可以进一步得到多面体先回顾一下矩阵与多面体的关系

线性约束表示多面体

多面体可以通过一组线性不等式来定义这些不等式可以表示为矩阵和向量的形式。

例如对于一个包含

m×n

多面体的顶点可以通过求解线性方程组通常涉及矩阵的逆或者伪逆来获得。

这些顶点是满足约束条件的解。

矩阵操作多面体

通过矩阵乘法可以对多面体进行线性变换如旋转、缩放、平移等。

例如如果矩阵M描述了一个线性变换那么多面体中的每一个点

仿射变换

仿射变换是线性变换的推广包括线性变换和平移。

可以用如下形式表示

yMxt

好吧其实矩阵和多面体与接下来要讲的算法也没多大关系笔者只是想说明如何从不等式推导到线性代数并扩展到多面体和高维空间体的。

使用Fourier-Motzkin算法

Fourier-Motzkin算法是一种经常在多面体中用于求解线性不等式系统的消去算法概括如下

选择消去变量

从程序中的优化出发由程序存储引出cache再由cache命中率引出数据局部性的重要性为了提高数据局部性必须改变循环遍历方法。

为了改变循环遍历方法由不等式引出线性代数再由线性代数引出多面体最后使用算法计算约束得到具有良好局部性的程序。

其实没啥好总结的只写了一小段还没写完开头呢不过先更到这该上床睡觉了。