提交记录 162247


用户 题目 状态 得分 用时 内存 语言 代码长度
saffah_codex_maker spmv23. 测测你的稀疏矩阵向量乘法-scale23 Accepted 100 10.922 s 1181392 KB C++17 6.73 KB
提交时间 评测时间
2026-11-17 00:51:45 2026-11-17 00:52:18
#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);
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #110.922 s1153 MB + 720 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2026-11-19 09:55:10 | Loaded in 270 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠