[Algorithms] Shors is too heavy! use up classical computer's resource

[xiangzhai]

Hi ScaffCC developers,

$ ./build/Release+Asserts/bin/clang --version
clang version 3.1 (tags/RELEASE_31/final)
Target: x86_64-unknown-linux-gnu
Thread model: posix

$ ./build/Release+Asserts/bin/opt --version
LLVM (http://llvm.org/):
  LLVM version 3.1
  Optimized build with assertions.
  Built Oct 23 2017 (16:22:51).
  Default target: x86_64-unknown-linux-gnu
  Host CPU: corei7-avx

$ ./scaffold.sh -fkR Algorithms/Shors/shors.n512.scaffold 
[Scaffold.makefile] Compiling shors.n512_merged.scaffold ...
[Scaffold.makefile] Transforming cbits ...
[Scaffold.makefile] O1 optimizations ... <-- CPU boiled
[Scaffold.makefile] Unrolling Loops (1) ... <-- press POWER to restart my computer

Perform loop unrolling until completely unrolled, then remove dead code is not able to work for Shors, but able to work for QFT:

$ ./scaffold.sh -fkR Algorithms/QFT/qft.n05.scaffold 
[Scaffold.makefile] Compiling qft.n05_merged.scaffold ...
[Scaffold.makefile] Transforming cbits ...
[Scaffold.makefile] O1 optimizations ...
[Scaffold.makefile] Unrolling Loops (1) ...
[Scaffold.makefile] Cloning Functions (1) ...
Functions Cloned: 2
[Scaffold.makefile] Dead Argument Elimination (1) ...
[Scaffold.makefile] Unrolling Loops (2) ...
[Scaffold.makefile] Cloning Functions (2) ...
Functions Cloned: 0
[Scaffold.makefile] Dead Argument Elimination (2) ...
[Scaffold.makefile] Internalizing and Removing Unused Functions ...
[Scaffold.makefile] Toffoli Decomposition ...
[Scaffold.makefile] Inserting Reverse Functions...
[Scaffold.makefile] Flattening modules ...
[Scaffold.makefile] Flat QASM written to qft.n05.qasmf ...

$ ./qft.n05_qasm 
PrepZ reg0
PrepZ reg1
PrepZ reg2
PrepZ reg3
PrepZ reg4
H reg0
T reg0
Rz reg1,0.785398
CNOT reg1,reg0
Rz reg1,-0.785398
CNOT reg1,reg0
H reg1
Rz reg0,0.392699
Rz reg2,0.392699
CNOT reg2,reg0
Rz reg2,-0.392699
CNOT reg2,reg0
T reg1
Rz reg2,0.785398
CNOT reg2,reg1
Rz reg2,-0.785398
CNOT reg2,reg1
H reg2
Rz reg3,-0.196350
CNOT reg3,reg0
Rz reg3,0.196350
CNOT reg3,reg0
Rz reg1,0.392699
Rz reg3,0.392699
CNOT reg3,reg1
Rz reg3,-0.392699
CNOT reg3,reg1
T reg2
Rz reg3,0.785398
CNOT reg3,reg2
Rz reg3,-0.785398
CNOT reg3,reg2
H reg3
Rz reg4,-0.098150
CNOT reg4,reg0
Rz reg4,0.098150
CNOT reg4,reg0
Rz reg4,-0.196350
CNOT reg4,reg1
Rz reg4,0.196350
CNOT reg4,reg1
Rz reg2,0.392699
Rz reg4,0.392699
CNOT reg4,reg2
Rz reg4,-0.392699
CNOT reg4,reg2
T reg3
Rz reg4,0.785398
CNOT reg4,reg3
Rz reg4,-0.785398
CNOT reg4,reg3
H reg4
H reg0
MeasZ reg0
H reg1
MeasZ reg1
H reg2
MeasZ reg2
H reg3
MeasZ reg3
H reg4
MeasZ reg4

I am also testing with scaff-llvm based on LLVM 6.0 to compile Shors :)

Regards, Leslie Zhai - a LLVM developer https://reviews.llvm.org/p/xiangzhai/

[xiangzhai]

LLVM 6.0 to compile Shors:

$ ./scaffold.sh -fkR Algorithms/Shors/shors.n512.scaffold 
[Scaffold.makefile] Compiling shors.n512_merged.scaffold ...
clang version 6.0.0 ([email protected]:llvm-mirror/clang.git 0aed123216ad4a38a9c2b16f1783895fd5cb1a04) ([email protected]:llvm-mirror/llvm.git d209b37aec1e392dabbf9b5324ea4a60c36fbc55)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /data/project/ScaffCC/ScaffCC/./build/bin
Found candidate GCC installation: /usr/lib/gcc/x86_64-redhat-linux/6.3.1
Found candidate GCC installation: /usr/lib/gcc/x86_64-redhat-linux/6.4.1
Selected GCC installation: /usr/lib/gcc/x86_64-redhat-linux/6.4.1
Candidate multilib: .;@m64
Candidate multilib: 32;@m32
Selected multilib: .;@m64
 "/data/project/ScaffCC/ScaffCC/build/bin/clang-6.0" -cc1 -triple x86_64-unknown-linux-gnu -emit-llvm -disable-free -main-file-name shors.n512_merged.scaffold -mrelocation-model static -mthread-model posix -mdisable-fp-elim -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -v -coverage-notes-file /data/project/ScaffCC/ScaffCC/shors.n512.gcno -resource-dir /data/project/ScaffCC/ScaffCC/build/lib/clang/6.0.0 -I Algorithms/Shors/ -internal-isystem /usr/local/include -internal-isystem /data/project/ScaffCC/ScaffCC/build/lib/clang/6.0.0/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -fdebug-compilation-dir /data/project/ScaffCC/ScaffCC -ferror-limit 19 -fmessage-length 103 -fobjc-runtime=gcc -fdiagnostics-show-option -fcolor-diagnostics -disable-O0-optnone -o shors.n512.ll -x c shors.n512_merged.scaffold
clang -cc1 version 6.0.0 based upon LLVM 6.0.0svn default target x86_64-unknown-linux-gnu
ignoring nonexistent directory "/include"
#include "..." search starts here:
#include <...> search starts here:
 Algorithms/Shors
 /usr/local/include
 /data/project/ScaffCC/ScaffCC/build/lib/clang/6.0.0/include
 /usr/include
End of search list.
[Scaffold.makefile] Transforming cbits ...
[Scaffold.makefile] O1 optimizations ...
[Scaffold.makefile] Unrolling Loops (1) ...
[Scaffold.makefile] Cloning Functions (1) ...
Functions Cloned: 453503
[Scaffold.makefile] Dead Argument Elimination (1) ... <--- CPU boiled...