注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

Day4《缓存规划》的满分做法  

2011-06-12 19:26:58|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
首先,让我们先想想怎么骗到7分(高逸涵的标程的得分)
首先,把一个内存位置a读到一个寄存器b可以用下面三句话完成:
L 2 0 a/20
L 1 0 a%20/10
L 0 b a%10
写入一个内存位置可以用5句话完成:
L 2 0 a/20
L 1 0 a%20/10
W 0 b a%10
W 1 0 a%20/10
W 2 0 a/20
注意到,我们在缓存之间的读写必须以10或20个为一组才能完成。
用这种方式暴力完成5个任务可以拿7分(如果你写的好,能拿9分)

下面,让我们来分析一下如何更高效一点地完成任务
想法1:分治
把一个4*4的矩阵转置,我们可以把它看做是2*2个2*2的小矩阵
a1 a2 b1 b2
a3 a4 b3 b4
c1 c2 d1 d2
c3 c4 d3 d4
把他们分别转置
a1 a3 b1 b3
a2 a4 b2 b4
c1 c3 d1 d3
c2 c4 d2 d4
之后再整体转置即可
a1 a3 c1 c3
a2 a4 c2 c4
b1 b3 d1 d3
b2 b4 d2 d4
从复杂度的角度上说,我们并没有优化任何东西,不过,在多级缓存的情况下,这个有重大意义!
对于50*50的矩阵的转置问题,我们可以把它分成5*5个10*10的小矩阵,
对每个小矩阵,把它加载到一级缓存中(我们可以10连续的数一起读写),在一级缓存中将它转置,之后再写回主存中对应的位置。
这样,就避免了大量的主存的读写操作。
对于100*100的矩阵,我们将它视作5*5个2*2个10*10的小矩阵,利用一级、二级缓存进行两次分治。

这样,前两个测试点就能拿满分了。

对于矩阵乘法,我们也可以把原先矩阵划分为10*10的小矩阵,把小矩阵加载到二级缓存(一级缓存连两个10*10的都存不下)来完成小矩阵之间的乘法,之后相加汇总。
这个方法能得68分左右。
我在考场上是怎么利用这种方法得到的91分的呢?我注意到:上面这个算法中在二级缓存中的小矩阵相乘的时候一级缓存只用了10个单位,空闲了90个,这显然不好;于是,我用这90个空间作为真正的缓存,把从二级缓存读入的数暂存到此,以后要把一个数加载到寄存器的时候先看一级缓存中是否已经有了。如果90个空间满了,就随机替换一个。
这个方法能得91分。具体地说,是测试点1、2、4、5能拿满,第3个点拿11分。

如何拿满分呢?

想法2:先转置后乘法
在多级缓存的情况下,计算两个连续的内存单位代表的向量的内积非常快速的(因为我们可以10个或20个一起加载)
但问题是矩阵乘法中是一个行向量和一个列向量的点积。怎么办呢?
那就先将第二个矩阵转置!
这样,就变成了行向量和行向量点积。
用这个方法做第3、4、5个测试点即可拿到满分了。
事实上,在C++中这个优化也是有作用的!
不信你就试试两个1000*1000的矩阵相乘,我测试得先转置后乘法比普通做法快了一倍(或许因为我的机器比较老)

下面是各个测试点的汇总:
编号 满分线 实际用时 得分
1 100000 89500 15
2 500000 158000 20
3 2000000 1872000 20
4 8000000 3471500 20
5 40000000 13278000 25
总分100

#include <cstdio>
#include <algorithm>
using namespace std;
FILE *fout;
int stat,lines=0,cnt=0;
void exe(char *buf,int t,int x,int y){
if (!stat){
lines++;
return;
}
fprintf(fout,"%s ",buf);
if (buf[0]=='A' || buf[0]=='M')
fprintf(fout,"%d %d\n",x,y);
else
fprintf(fout,"%d %d %d\n",t,x,y);
if (t==0)cnt++;
else if (t==1)cnt+=20;
else cnt+=100;
}
namespace work2{
void trans0(){
for (int i=0;i<10;i++)
for (int j=0;j<i;j++){
exe("L",0,0,i*10+j);
exe("L",0,1,j*10+i);
exe("W",0,1,i*10+j);
exe("W",0,0,j*10+i);
}
}
void trans1(){
for (int i=0;i<2;i++)
for (int j=0;j<2;j++){
for (int k=0;k<10;k++){
exe("L",1,k,((i*10+k)*20+(j*10))/10);
}
trans0();
for (int k=0;k<10;k++){
exe("W",1,k,(400+(j*10+k)*20+(i*10))/10);
}
}
}
void work2(){
for (int i=0;i<5;i++)
for (int j=0;j<5;j++){
for (int k=0;k<20;k++){
exe("L",2,k,((i*20+k)*100+(j*20))/20);
}
trans1();
for (int k=0;k<20;k++){
exe("W",2,20+k,(10000+(j*20+k)*100+(i*20))/20);
}
}
}
void LoadRaw12(int a,int z){
exe("L",2,0,a/20);
exe("L",1,z,a%20/10);
}
void WriteRaw12(int a,int z){
exe("L",2,0,a/20);
exe("W",1,z,a%20/10);
exe("W",2,0,a/20);
}
void work1(){
for (int i=0;i<5;i++)
for (int j=0;j<5;j++){
for (int k=0;k<10;k++){
LoadRaw12((i*10+k)*50+(j*10),k);
}
trans0();
for (int k=0;k<10;k++){
WriteRaw12(2500+(j*10+k)*50+(i*10),k);
}
}
}
}
namespace work3{
void LoadRaw(int a,int z=0){
exe("L",2,0,a/20);
exe("L",1,0,a%20/10);
exe("L",0,z,a%10);
}
void WriteRaw(int a,int z=0){
exe("L",2,0,a/20);
exe("L",1,0,a%20/10);
exe("W",0,z,a%10);
exe("W",1,0,a%20/10);
exe("W",2,0,a/20);
}
void get2(int a,int l,int z){
int p=a-a%20;
for (int i=0;i<l;i+=20)
exe("L",2,z+i/20,(p+i)/20);
}
void get21(int a,int q,int p,int z){
a=a%20/10;
exe("L",1,z/10,q*2+p/10+a);
}
void WriteB(int a,int z=0){
exe("W",0,z,90+a%10);
if (a%10==9){
exe("W",1,9,49*2+a%20/10);
if (a%20==19)
exe("W",2,49,a/20);
}
}
void work3(){
for (int i=0;i<5;i++)
for (int j=0;j<5;j++){
for (int k=0;k<10;k++){
work2::LoadRaw12(2500+(i*10+k)*50+(j*10),k);
}
work2::trans0();
for (int k=0;k<10;k++){
work2::WriteRaw12(7500+(j*10+k)*50+(i*10),k);
}
}
for (int i=0;i<50;i++){
int u1=i*50;
get2(u1,50,0);
for (int j=0;j<50;j++){
int u2=7500+j*50;
get2(u2,50,3);
for (int k=0;k<5;k++){
get21(u1,0,k*10,0);
get21(u2,3,k*10,10);
for (int l=0;l<10;l++){
if (k==0 && l==0){
exe("L",0,0,0);
exe("L",0,1,10);
exe("M",0,0,1);
}else{
exe("L",0,1,l);
exe("L",0,2,10+l);
exe("M",0,1,2);
exe("A",0,0,1);
}
}
}
WriteB(5000+i*50+j);
}
}
}
void work5(){
for (int i=0;i<5;i++)
for (int j=0;j<5;j++){
for (int k=0;k<20;k++){
exe("L",2,k,(10000+(i*20+k)*100+(j*20))/20);
}
work2::trans1();
for (int k=0;k<20;k++){
exe("W",2,20+k,(30000+(j*20+k)*100+(i*20))/20);
}
}
for (int i=0;i<100;i++){
int u1=i*100;
get2(u1,100,0);
for (int j=0;j<100;j++){
int u2=30000+j*100;
get2(u2,100,5);
for (int k=0;k<10;k++){
get21(u1,0,k*10,0);
get21(u2,5,k*10,10);
for (int l=0;l<10;l++){
if (k==0 && l==0){
exe("L",0,0,0);
exe("L",0,1,10);
exe("M",0,0,1);
}else{
exe("L",0,1,l);
exe("L",0,2,10+l);
exe("M",0,1,2);
exe("A",0,0,1);
}
}
}
WriteB(20000+i*100+j);
}
}
}
void work4(){
for (int i=0;i<10;i++)
for (int j=0;j<5;j++){
for (int k=0;k<10;k++){
work2::LoadRaw12(5000+(i*10+k)*50+(j*10),k);
}
work2::trans0();
for (int k=0;k<10;k++){
work2::WriteRaw12(15000+(j*10+k)*100+(i*10),k);
}
}
for (int i=0;i<50;i++){
int u1=i*100;
get2(u1,100,0);
for (int j=0;j<50;j++){
int u2=15000+j*100;
get2(u2,100,5);
for (int k=0;k<10;k++){
get21(u1,0,k*10,0);
get21(u2,5,k*10,10);
for (int l=0;l<10;l++){
if (k==0 && l==0){
exe("L",0,0,0);
exe("L",0,1,10);
exe("M",0,0,1);
}else{
exe("L",0,1,l);
exe("L",0,2,10+l);
exe("M",0,1,2);
exe("A",0,0,1);
}
}
}
WriteB(10000+i*50+j);
}
}
}
}
int main()
{
FILE *fin=fopen("cache.in","r");
fout=fopen("cache.out","w");
int T;
fscanf(fin,"%d",&T);
for (stat=0;stat<2;stat++){
lines=0;cnt=0;
srand(1);
if (T==1)work2::work1();
else if (T==2)work2::work2();
else if (T==3)work3::work3();
else if (T==4)work3::work4();
else if (T==5)work3::work5();
if (stat==0)fprintf(fout,"%d\n",lines);
}
fclose(fin);fclose(fout);
return 0;
}

  评论这张
 
阅读(1043)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017