1. 报告要求
- 并行化
- 提高运行速度
- 突显cache友好
- 对比实验
- 对关键步骤描述算法
2. 初步草案
- 选择实现语言。我选择了较为熟悉的python作为编程语言。因为python的库numpy在底层调用c与fortran,并且采用优化过的算法,因此在矩阵运算方面速度极高。
- 选择预测方法。由于要突显cache友好,且实现并行化,我认为logistic regression能符合要求。
- 选择训练方式。训练方式不外乎三种:BGD, mini BGD, SGD。其中SGD在运行中占用的内存最小(每次处理一组数据即可)。因此,我将会对三种训练方式进行考察,并着重观察SGD。
- 选择并行化的解决方案。使用python内置的multiprocessing库即可。并验证按参数并行运算和分批并行运算的速度比较。
3. 并行化解决方案
3.1 按参数并行运算
梯度计算函数
def compute_sum(parameters, result, data_array, theta, number_of_examples):
for parameter in parameters: # [n, n+1, n+2, ..., m]
summition = 0
for sample in data_array:
# (hypothesis - real_value) * feature_i
summition += (hypothesis(sample[:-1], theta) - sample[-1]) * sample[parameter]
result[parameter] = summition / number_of_examples # gradient for feature_i
运行结果: