Accelerate

发表于 更新于 分类于 阅读次数：

0x00 前言

这篇文章是自己在学习 CFHipsterRef Chapter 9 Accelerate 时做的笔记。

0x01 Accelerate

在过去的十年里，当涉及到硬件是，一直专注于以更少的方式做更多。

随着每一代微处理器推动着硅的物理极限，更多的重点放在以更少的方式做更多。摩尔定律，观察到可以安装到芯片上的晶体管的数量每 18 个月左右就翻一倍，会在某个时间停止，而且那个时间也很快接近。

与此同时，移动计算的崛起改变了其性能范式，强调电池寿命超过功率（over power）。

为了响应这两个新兴的现实，硬件制造商已经制造了多核 CPU，软件开发者已经学会了利用高并行和并发。

在 iOS 和 OS X 上，利用这些高级功能的最佳方法是 Accelerate 框架。

通过超过 2,000 个 API，Accelerate 很容易成为 iOS 和 OS X SDK 中最大的框架。但远不止大，它更像是一个伞框架（umbrella framework，使用苹果的术语，封装了其他框架的框架通常称为 umbrella framework），有几个互相关联的组件。

在顶层，Accelerate 可以在 vecLib & vImage 之间分离。vecLib 包含用于数字信号处理（vDSP）以及矢量和矩阵运算的数据类型和 C 函数，包括线性代数包（Linear Algebra Package，LAPACK）和基础线性代数子程序（Basic Linear Algebra Subprograms，BLAS）标准涵盖的那些。vImage 包含一个广泛的图像操作功能，包括 alpha 合成，转换（conversion），卷积（convolution），形态（morphology），变换（transformation）和直方图（histogram）生成。

学习使用 Accelerate 只是在 API 数量方面可以是压倒性的。对于任何没有数学或高性能计算背景的人来说，仅概念理解就足够吓跑很多人。

0x02 SIMD

如果 Accelerate 有一个统一的概念，那就是 SIMD，或者说 “单指令，多数据”。SIMD 意味着一个计算机可以使用单个命令同时对多个数据点执行相同的操作。

例如，给定一个无符号的整型数组，其最大值可以是单个优化的硬件指令（例如，用于 SSE 的 PMAXUB）所能找到的最大值。

在 iPhone，iPad 和 Mac 中找到的硬件拥有令人印象深刻的功能。在 x86 架构（Mac）上，关键技术是 SSE，AVX 和 AVX2；对于 AMD（iPhone & iPad），则是 NEON。

Acc 提供了单个统一的 API 集，适应在所有这些不同结构和硬件环境提供相同的行为，以确保最大的性能和稳定性，而无需任何编译标志或平台 hack。

0x03 Benchmarking Performance

这些高级例程在实践中产生了多大的不同？考虑以下常见算术运算的基准（benchmarks）：

0x0301 Populating an Array

1
2
NSUInteger count = 1000000;
float *array = malloc(count * sizeof(float));

Baseline

1
2
3
for (NSUInteger i = 0; i < count; i++) {
    array[i] = i;
}

Accelerate

1
2
3
float initial = 0;
float increment = 1;
vDSP_vramp(&initial, &increment, array, 1, count);
Baseline Accelerate △
20.664600 msec 2.495000 msec 10x

0x0302 Multiplying an Array

Baseline

1
2
3
for (NSUInteger i = 0; i < count; i++) {
    array[i] *= 2.0f;
}

Accelerate

1
cblassscal(count, 2.0f, array, 1);
Baseline Accelerate △
19.969440 msec 2.541220 msec 10x

0x0303 Summing an Array

Baseline

1
2
3
4
float sum = 0;
for (NSUInteger i = 0; i < count; i++) {
    sum += array[i];
}

Accelerate

1
float sum = cblas_sasum(count, array, 1);
Baseline Accelerate △
41.704483 msec 2.165160 msec 20x

0x0304 Searching

Create random array

1
2
3
for (NSUInteger i = 0; i < count; i++) {
    array[i] = (float)arc4random();
}

Baseline

1
2
3
4
5
6
NSUInteger MaxLocation = 0;
for (NSUInteger i = 0; i < count; i++) {
    if (array[i] > array[maxLocation]) {
        maxLocation = i;
    }
}

Accelerate

1
NSUInteger maxLocation = cblas_isamax(count, array, 1);
Baseline Accelerate △
22.339838 msec 5.110880 msec 4x

从这些基准，很明显，对于大数据集，Accelerate 可以获得巨大的性能优势。当然，就像任何优化一样，并非所有情况都会同样受益。最好的方法是始终使用 Instruments 来发现代码中的瓶颈，并估算替代的实现。

为了理解和识别可能从 Accelerate 中获益的情况，不过，我们需要知道它能做什么。

0x0305 vecLib

vecLib 是由以下 9 个头文件构成：
cblas.h / vBLAS.h Interface for BLAS functions
clapack.h Interface for LAPACK functions
vectorOps.h Vector implementations of the BLAS routines.
vBasicOps.h Basic algebraic operations. 8-, 16-, 32-, 64-, 128-bit division, saturated addition / subtraction, shift / rotate, etc.
vfp.h Transcendental operations (sin, cos, log, etc.) on single vector floating point quantities.
vForce.h Transcendental operations on arrays of floating point quantities.
vBigNum.h Operations on large numbers (128-, 256-, 512-, 1024-bit quantities)
vDSP.h Digital signal processing algorithms including FFTs, signal clipping, filters, and type conversions.

xDSP.h

快速傅里叶变换（Fast-Fourier Transform, FFT）是基本数字信号处理算法。它将一系列值分解成具有不同频率（different frequencies）的分量（components）。

尽管它们在数学和工程方面具有广泛的应用，但是大多数应用程序开发者遇到用于音频或视频处理的 FFT，作为一种确定噪声信号中的临界值的方式。

快速傅里叶变换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int x = 8;
int y = 8;

int dimensions = x * y;

int log2_x = (int)log2((double)x);
int log2_y = (int)log2((double)y);

DSPComplex *data = (DSPComplex *)malloc(sizeof(DSPComplex) * dimensions);
for (NSUInteger i = 0; i < dimensions; i++) {
   data[i].real = (float)i;
   data[i].imag = (float)(dimensions - i) - 1.0f; 
}

DSPSplitComplex input = {
   .realp = (float *)malloc(sizeof(float) * dimensions),
   .imagp = (float *)malloc(sizeof(float) * dimensions),
};

vDSP_ctoz(data, 2, &input, 1, dimensions);

FFTSetup weights = vDSP_create_fftsetup(fmax(log2_x, log2_y), kFFTRadix2);
vDSP_fft2d_zip(weights, &inout, 1, 0, log2_x, log2_y, FFT_FORWARD);
vDSP_destroy_fftsetup(fft_weights);

vDSP_ztoc(&input, 1, data, 2, dimensions);

for (NSUInteger i = 0; i < dimensions; i++) {
    NSLog(@"%g %g", data[i].real, data[i].imag);
}

free(input.realp);
free(input.imagp);
free(data);

vImage

vImage 是由 6 个头文件组成：
Alpha.h Alpha 合成方法（Alpha compositing functions）
Conversion.h 图像之间转换（Converting between image format）（e.g. Planar8 to PlanarF, ARGB8888 to Planar8）
Convolution.h Image convolution routines (e.g. blurring and edge detection).
Geometry.h 几何变换（Geometric transformations）（e.g. rotate, scale, shear, affine warp）
Histogram.h 用于计算图像直方图和图像归一化的函数（Functions for calculating image histograms and image normalization）
Morphology.h 图像形态程序（Image morphology procedures）（e.g. feature detection, dilation, erosion）
Tranform.h 图像变换操作（Image transformation operations）（e.g. gamma correction, colorspace conversion）
Planar8 图像是单个通道（一种颜色或 alpha 值）。每个像素是 8 位无符号整型值。此图像格式的数据类型为 Pixel_8。
PlanarF 图像是单个通道（一种颜色）。每个像素是 32 位浮点数值。此图像格式的数据类型是 Pixel_F。
ARGB8888 图像有 4 个交错的通道，alpha，red，green 和 blue，以该顺序。每个像素是 32 位，由 4 个 8 位无符号整型组成的数组。此图像格式的数据类型是 Pixel_8888。
ARGBFFFF 图像有 4 个交错的通道，alpha，red，green 和 blue，以该顺序。每个像素是 由 4 个浮点数组成的数组。此图像格式的数据类型是 Pixel_FFFF。
RGBA8888 图像有 4 个交错的通道，alpha，red，green 和 blue，以该顺序。每个像素是 32 位，由 4 个 8 位无符号整型组成的数组。此图像格式的数据类型是 Pixel_8888。
RGBAFFFF 图像有 4 个交错的通道，alpha，red，green 和 blue，以该顺序。每个像素是 由 4 个浮点数组成的数组。此图像格式的数据类型是 Pixel_FFFF。

Alpha.h

Alpha 合成是根据其 alpha 分量（components）组合多个图像的过程。对于一个图像的每一个像素，用 alpha 或 透明度的值来确定有多少图像将在下方显示。

vImage 方法可用于混合或剪切。最常见的操作是将一个顶部图像合成到底部图像上：

Compositing Two Images
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
UIImage *topImage, bottomImage = ...;
CGImageRef topImageRef = [topImage CGImage];
CGImageRef bottomImageRef = [bottomImage CGImage];

CGDataProviderRef topRrovider = CGImageGetDataProvider(topImageRef);
CFDataRef topBitmapData = CGDataProviderCopyData(topProvider);

size_t width = CGImageGeiWidth(topImageRef);
size_t height = CGImageGeiHeight(topImageRef);
size_t bytesPerRow = CGImageGetBytesPerRow(topImageRef);

vImage_Buffer topBuffer = {
    .data = (void *)CFDataGetBytePtr(topBitmapData),
    .width = width,
    .height = height,
    .rowBytes = bytesPerRow,
};

CGDataProviderRef bottomProvider = CGImageGetDataProvider(bottomImageRef);
CFDataRef bottomBitmapData = CGDataProviderCopyData(bottomProvider);

vImage_Buffer bottomBuffer = {
    .data = (void *)CFDataGetBytePtr(bottomBitmapData),
    .width = width,
    .height = height,
    .rowBytes = bytesPerRow,
};

void *outBytes = malloc(height * bytesPerRow);
vImage_Buffer outBuffer = {
    .data = outBytes,
    .width = width,
    .height = height,
    .rowBytes = bytesPerRow,
};

vImage_Error error = vImagePremultipliedAlphaBlend_ARGB8888(&topBuffer, &buttomBuffer, &outBuffer, kvImageDoNotTile);

if (error) {
    NSLog(@"Error: %ld", error);
}

Conversion.h

图像由像素组成，每个像素具有一个红色，绿色和蓝色强度的离散值的组合表示的颜色。总之，这些强度值构成每个颜色的一个通道，以及一个 alpha 通道，代表透明度。

有两种图像对该信息进行编码的方式： 交错 （interleaved），这样每个像素有共同表示的红，绿，蓝和 alpha 值，或 平面 （planar），其中设置了一个通道中的所有值，然后是下一个通道中的值，以此类推。

对于给定图像格式，vImage 提供了用于将强度从一个通道交换到另一个通道的方法：

Permuting Color Channels
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
UIImage *image = ...;
CGImageRef imageRef = [image CGImage];

size_t width = CGImageGetWidth(imageRef);
size_t height = CGImageGetHeight(imageRef);
size_t bitsPerComponent = CGImageGetBitsPerComponent(imageRef);
size_t bytesPerRow = CGImageGetBytesPerRow(imageRef);

CGDataProviderRef sourceImageDataProvider = CGImageGetDataProvider(imageRef);
CFDataRef sourceImageData = CGDataProviderCopyData(sourceImageDataProvider);
vImage_Buffer sourceImageBuffer = {
    .data = (void *)CFDataGetBytePtr(sourceImageData),
    .width = width,
    .height = height,
    .rowBytes = bytesPerRow,
};

uint8_t *destinationBuffer = malloc(CFDataGetLength(sourceImageData));
vImage_Buffer destinationImageBuffer = {
    .data = destinationBuffer,
    .width = width,
    .height = height,
    .rowBytes = bytesPerRow,
};

const uint8_t channels[4] = {0, 3, 2, 1}; // ARGB -> ABGR
vImagePermuteChannels_ARGB8888(&sourceImageBuffer, &destinationImageBuffer, channels, kvImageNoFlags);

CGColorSpaceRef colorSpaceRef = CGColorSpaceCreateDeviceRGB();
CGContextRef destinationContext =
    CGBitmapContextCreateWithData(destinationBuffer,
                                  width,
                                  height,
                                  bitsPerComponent,
                                  bytesPerRow,
                                  colorSpaceRef,
                                  kCGBitmapByteOrderDefault |
                                  kCGImageAlphaPermultipliedFirst,
                                  NULL,
                                  NULL);

CGImageRef permutedImageRef = CGBitmapContextCreateImage(destinationContext);
UIImage *permutedImage = [UIImage imageWithCGImage:permutedImageRef];

CGImageRelease(permutedImageRef);
CGContextRelease(destinationContext);
CGColorSpaceRelease(colorSpaceRef);

Convolution.h

图像卷积（Image convolution）是将每个像素及其相邻的像素乘以 内核 （kernel），或用和为 1 的正方形矩阵。取决于这个内核，一个卷积操作可以是模糊（blur），锐化（sharpen），浮雕（emboss）或边缘检测（detect edges）。

除了需要一个定制内核的特殊情况，利用 GPU，卷积操作通过 Core Image 框架将被更好地服务（better-served）。然而，对于一个直接基于 GPU 的解决方案，vImage 提供了：

Blurring an Image
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
UIImage *inImage = ...;
CGImageRef = inImageRef = [inImage CGImage];

CGDataProviderRef inProvider = CGImageGetDataProvider(inImageRef);
CFDataRef inBitmapData = CGDataProviderCopyData(inProvider);

vImage_Buffer inBuffer = {
    .data = (void *)CFDataGetBytePtr(inBitmapData),
    .width = CGImageGetWidth(inImageRef),
    .height = CGImageGetHeight(inImageRef),
    .rowBytes = CGImageGetBytesPerRow(inImageRef),
};

void *outBytes = malloc(CGImageGetBytesPerRow(inImageRef) * CGImageGetHeight(inImageRef));
vImage_Buffer outBuffer = {
    .data = outBuffer,
    .width = inBuffer.width,
    .height = inBuffer.height,
    .rowBytes = inBuffer.rowBytes,
};

uint32_t length = 5; // Size of convolution
vImage_Error error = vImageBoxConvolve_ARGB8888(&inBuffer, &outBuffer, NULL, 0, 0, length, length, NULL, kvImageEdgeExtend);

if (error) {
    NSLog(@"Error: %ld", error);
}

CGColorSpaceRef colorSpaceRef = CGColorSpaceCreateDeviceRGB();
CGContextRef c = CGBitmapContextCreate(outBuffer.data, outBuffer.width, outBuffer.height, 8, outBuffer.rowBytes, colorSpaceRef, kCGImageAlphaNoneSkipLast);
CGImageRef outImageRef = CGBitmapContextCreateImage(c);
UIImage *outImage = [UIImage imageWithCGImage:outImageRef];

CGImageRelease(outImageRef);
CGContextRelease(c);
CGColorSpaceRelease(colorSpaceRef);
CFRelease(inBitmapData);

Geometry.h

调整一个图像大小是另一种操作，可能更适合于另一个基于 GPU 的框架，如 Image I/O。对于一个给定的 vImage buffer，使用 Accelerate 的 vImageScale_* 可能性能更高，而不是在 CGImageRef 之间来回转换：

Resizing an Image
1
2
3
4
5
6
7
8
9
10
11
12
13
double scaleFactor = 1.0 / 5.0;
void *outBytes = malloc(trunc(inBuffer.height * scaleFactor) * inBuffer.rowBytes);
vImage_Buffer outBuffer = {
    .data = outBytes,
    .width = trunc(inBuffer.width * scaleFactor),
    .height = trunc(inBuffer.height * scaleFactor),
    .rowBytes = inBuffer.rowBytes,
};

vImage_Error error = vImageScale_ARGB8888(&inBuffer, &outBuffer, NULL, kvImageHighQualityResampling);
if (error) {
    NSLog(@"Error: %ld", error);
}

Histogram.h

检测一个图像是否包含透明度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
UIImage *image;
CGImage imageRef = [image CGImage];
CGDataProviderRef dataProvider = CGImageGetDataProvider(imageRef);
CFDataRef = bitmapData = CGDataProviderCopyData(dataProvider);

vImagePixelCount a[256], r[256], g[256], b[256];
vImagePixelCount *histogram[4] = {a, r, g, b};
vImage_Buffer buffer = {
    .data = (void *)CFDataGetBytePtr(bitmapData),
    .width = CGImageGetWidth(imageRef),
    .height = CGImageGetHeight(imageRef),
    .rowBytes = CGImageGetByesPerRow(imageRef),
};

vImage_Error error = vImageHistogramCalculation_ARGB8888(&buffer, histogram, kvImageNoFlags);
if (error) {
    NSLog(@"Error: %ld", error);
}

BOOL hasTransparency = NO;
for (NSUInteger i = 0; !hasTransparency && i < 255; i++) {
    hasTransparency = histogram[3][i] == 0;
}

CGDataProviderRelease(dataProvider);
CFRelease(bitmapData);

Morphology.h

扩大图像（Dilating an Image）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
size_t width = image.size.width;
size_t height = image.size.height;
size_t bitsPerComponent = 8;
size_t bytesPerRow = CGImageGetBytesPerRow([image CGImage]);

CGColorSpaceRef colorSpaceRef = CGColorSpaceCreateDeviceRGB();
CGContextRef sourceContext =
    CGBitmapContextCreate(NULL,
                          width,
                          height,
                          bitsPerComponent,
                          bytesPerRow,
                          colorSpaceRef,
                          kCGBitmapByteOrderDefault |
                          kCGImageAlphaPremultipliedFirst);

CGContextDrawImage(sourceContext, CGRectMake(0.0f, 0.0f, width, height), [image CGImage]);

void *sourceData = CGBitmapContextGetData(sourceContext);
vImage_Buffer sourceBuffer = {
    .data = sourceData,
    .width = width,
    .height = height,
    .rowBytes = bytesPerRow,
};

size_t length = height * bytesPerRow;
void *destinationData = malloc(length);
vImage_Buffer destinationBuffer = {
    .data = destinationData,
    .width = width,
    .height = height,
    .rowBytes = bytesPerRow,
};

static unsigned char kernel[9] = {
    1, 1, 1,
    1, 1, 1,
    1, 1, 1,
};

vImageDilate_ARGB8888(&sourceBuffer, &destinationBuffer, 0, 0, kernel, 9, 9, kvImageCopyInPlace);

CGContextRef destinationContext =
    CGBitmapContextCreateWithData(destinationData,
                                  width,
                                  height,
                                  bitsPerComponent,
                                  bytesPerRow,
                                  colorSpaceRef,
                                  kCGBitmapByteOrderDefault |
                                  kCGImageAlphaPremultipliedFirst,
                                  NULL,
                                  NULL);

CGImageRef dilatedImageRef = CGBitmapContextCreateImage(destinationContext);
UIImage *dilatedImage = [UIImage imageWithCGImage:dilatedImageRef];

CGImageRelease(dilatedImageRef);
CGContextRelease(destinationContext);
CGContextRelease(sourceContext);
CGColorSpaceRelease(colorSpaceRef);

在这个广泛监视，减少隐私和无处不在的连接的时代，安全不再是偏执狂的宠物主题 —— 这是每个人都能很好理解的东西。

安全框架可以分为 Keychain Services，Cryptographic Message Syntax，Security Transform Services 和 CommonCrypto。

0x04 Keychain Services

Keychain 是 iOS 和 OS X 上的密码管理系统。它存储证书和私钥，以及网站，服务器，无线网络和其他加密卷（encrypted volumes）的密码。