#include <bits/stdc++.h>
#include <stdint.h>
#include <stddef.h>
#include <stdlib.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#ifndef DUCK_SPMV_EDGE_DEFINED
#define DUCK_SPMV_EDGE_DEFINED
struct Edge { unsigned src,dst,weight; };
#endif
static_assert(sizeof(unsigned)==4 && sizeof(Edge)==12,"Duck32-bit COO ABI");
// Exact directed COO -> SoA CSR, with 8-record non-temporal bucket writes.
// At most seven zero-weight records are appended to each 512-row bucket.
// Caller reserves m + 7*ceil(n/512) records in column and weight (32B aligned).
#include <immintrin.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
namespace sparse_stream {
struct Record { unsigned src,dst,weight; };
struct alignas(32) Fifo { unsigned key[8],val[8]; };
template<class GetSource,class GetRecord>
static unsigned build(unsigned n,unsigned m,GetSource get_source,GetRecord get_record,
unsigned*offset,unsigned*column,unsigned*weight) {
if(n>(1u<<23)||(!n&&m))abort();
constexpr unsigned bits=9,rows=1u<<bits,mask=rows-1;
const unsigned bins=(n+mask)>>bits;
unsigned*count=(unsigned*)calloc(bins,4);
unsigned*start=(unsigned*)malloc(((size_t)bins+1)*4);
unsigned*cursor=(unsigned*)malloc(((size_t)bins+1)*4);
unsigned char*fill=(unsigned char*)calloc(bins,1);
Fifo*fifo=nullptr;if(posix_memalign((void**)&fifo,32,(size_t)bins*sizeof(Fifo)))abort();
if(!count||!start||!cursor||!fill)abort();
for(unsigned e=0;e<m;++e)++count[get_source(e)>>bits];
unsigned padded=0;
for(unsigned b=0;b<bins;++b){start[b]=padded;padded+=(count[b]+7)&~7u;}
start[bins]=padded;memcpy(cursor,start,((size_t)bins+1)*4);
for(unsigned e=0;e<m;++e){auto r=get_record(e);unsigned b=r.src>>bits,j=fill[b];
fifo[b].key[j]=(r.dst<<bits)|(r.src&mask);fifo[b].val[j]=r.weight;
if(j==7){_mm256_stream_si256((__m256i*)(column+cursor[b]),_mm256_load_si256((const __m256i*)fifo[b].key));
_mm256_stream_si256((__m256i*)(weight+cursor[b]),_mm256_load_si256((const __m256i*)fifo[b].val));
cursor[b]+=8;fill[b]=0;}else fill[b]=j+1;
}
_mm_sfence();
for(unsigned b=0;b<bins;++b){unsigned rowcount=n-(b<<bits);if(rowcount>rows)rowcount=rows;
const unsigned j=fill[b],at=cursor[b];memcpy(column+at,fifo[b].key,j*4);memcpy(weight+at,fifo[b].val,j*4);
for(unsigned p=at+j;p<start[b+1];++p){column[p]=rowcount-1;weight[p]=0;}
}
for(unsigned b=0;b<bins;++b){unsigned histogram[rows]={},next[rows],end[rows];
const unsigned begin=start[b],stop=start[b+1],rowbase=b<<bits;
for(unsigned p=begin;p<stop;++p)++histogram[column[p]&mask];
const unsigned rowcount=n-rowbase<rows?n-rowbase:rows;unsigned first=begin;
for(unsigned r=0;r<rowcount;++r){offset[rowbase+r]=next[r]=first;first+=histogram[r];end[r]=first;}
for(unsigned r=0;r<rowcount;++r)while(next[r]<end[r]){unsigned p=next[r],key=column[p]&mask;
if(key==r){++next[r];continue;}unsigned q=next[key]++,c=column[p],w=weight[p];
column[p]=column[q];weight[p]=weight[q];column[q]=c;weight[q]=w;
}
for(unsigned p=begin;p<stop;++p)column[p]>>=bits;
}
offset[n]=padded;free(fifo);free(fill);free(cursor);free(start);free(count);return padded;
}
}
// Exact coordinate permutation for CSR20. The heuristic orders vector entries
// by coarse log2 row degree, highest-degree vertices first. This does not
// assume a DAG, a seed, or any particular Graph500 vertex permutation.
// Row storage stays unchanged; columns and vector coordinates are relabelled.
#include <immintrin.h>
#include <stdint.h>
#include <string.h>
namespace sparse_degree {
static unsigned degree_bin(unsigned d){return d?32u-(unsigned)__builtin_clz(d):0u;}
// perm maps an original vertex number to a unique new vector position.
static void make_permutation(unsigned n,const unsigned*offset,unsigned*perm){
unsigned count[33]={},next[33];
for(unsigned i=0;i<n;++i)++count[degree_bin(offset[i+1]-offset[i])];
unsigned first=0;
for(unsigned b=33;b-->0;){next[b]=first;first+=count[b];}
for(unsigned i=0;i<n;++i)perm[i]=next[degree_bin(offset[i+1]-offset[i])]++;
}
static void map_columns(unsigned m,unsigned*column,const unsigned*perm){
for(unsigned p=0;p<m;++p)column[p]=perm[column[p]];
}
// This step expects already mapped columns and an already permuted x.
// Writes also use perm, so no per-round vector rearrangement is needed.
static __attribute__((noinline,noclone)) void step(
unsigned n,const unsigned*offset,const unsigned*column,const unsigned*weight,
const unsigned*perm,const unsigned*x,unsigned*y){
for(unsigned i=0;i<n;++i){
unsigned p=offset[i],end=offset[i+1],sum=0;
if(end-p>=16){
__m256i acc=_mm256_setzero_si256();
for(;p+8<=end;p+=8){
__m256i index=_mm256_loadu_si256((const __m256i*)(column+p));
__m256i weights=_mm256_loadu_si256((const __m256i*)(weight+p));
__m256i selected=_mm256_i32gather_epi32((const int*)x,index,4);
acc=_mm256_add_epi32(acc,_mm256_mullo_epi32(weights,selected));
}
__m128i s=_mm_add_epi32(_mm256_castsi256_si128(acc),_mm256_extracti128_si256(acc,1));
s=_mm_add_epi32(s,_mm_shuffle_epi32(s,0x4e));
s=_mm_add_epi32(s,_mm_shuffle_epi32(s,0xb1));
sum=(unsigned)_mm_cvtsi128_si32(s);
}
for(;p<end;++p)sum+=weight[p]*x[column[p]];
y[perm[i]]=sum;
}
}
// Destructively maps the private CSR columns once. Input x stays const.
// caller supplies perm[n] and temp[n]; out[n] is the second iteration vector.
// Exactly20 rounds ensure the final permuted result is in temp, then a final
// inverse coordinate copy writes the original vertex order into out.
static void twenty(unsigned n,unsigned m,const unsigned*offset,unsigned*column,
const unsigned*weight,const unsigned*x,unsigned*out,
unsigned*temp,unsigned*perm){
make_permutation(n,offset,perm);map_columns(m,column,perm);
for(unsigned i=0;i<n;++i)temp[perm[i]]=x[i];
const unsigned*cur=temp;
for(unsigned r=0;r<20;++r){unsigned*dst=(r&1)?temp:out;step(n,offset,column,weight,perm,cur,dst);cur=dst;}
for(unsigned i=0;i<n;++i)out[i]=temp[perm[i]];
}
}
// No generator, seed, input table, or precomputed answer is present.
static void* allocate4096(size_t bytes){void*p=nullptr;if(posix_memalign(&p,4096,bytes))abort();return p;}
void sparse_power20(unsigned n,unsigned m,const Edge* A,const unsigned*x,unsigned*out){
const unsigned bins=(n+511)/512,capacity=m+7*bins;
unsigned*off=(unsigned*)allocate4096(((size_t)n+1)*4);
unsigned*col=(unsigned*)allocate4096((size_t)capacity*4);
unsigned*val=(unsigned*)allocate4096((size_t)capacity*4);
unsigned*temp=(unsigned*)allocate4096((size_t)n*4);
unsigned*perm=(unsigned*)allocate4096((size_t)n*4);
unsigned used=sparse_stream::build(n,m,[&](unsigned e){return A[e].src;},[&](unsigned e){return A[e];},off,col,val);
sparse_degree::twenty(n,used,off,col,val,x,out,temp,perm);
free(perm);free(temp);free(val);free(col);free(off);
}
| Compilation | N/A | N/A | Compile OK | Score: N/A | 显示更多 |
| Testcase #1 | 10.922 s | 1153 MB + 720 KB | Accepted | Score: 100 | 显示更多 |