optimization of SASS stall counts

Optimal instructions scheduling is NP-hard task. For this reason almost all compilers implement metaheuristic methods like list scheduling/Gibbons–Muchnick algorithm etc. ptxas is no exception - it also generates non-optimal scheduling, and this opens some opportunity for automatic optimization. Here I want to present scheduling model for SASS, tool for optimization of stall counts for binary CUBIN files, achieved results and possible direction for further improvements

First version

Has name dg.pl and used latency table extracted from ptxas with RE. Unfortunately it has at least 2 fatal flaws

1. This latency table is incomplete - for example some instructions like PRET/BFE/ICMP are missed. I tried to find similar table in more old ptxas versions - like 12, 11 and even 9 - it seems that they all incomplete
2. It takes into account only Read after Write joints and patched code crashed in random places, and on each launch in different places

After considerable and agonizing reflection, I concluded that it had used an incorrect model

so I decided to continue experiments with latency tables early extracted from nvdisasm

Latency tables

We can observe 3 types of tables in these files

TABLE_TRUE - it is quite obvious that this is Read after Write (RaW), row is write instruction, column is read. We can assume that this order is always the same - first instruction connecting by row and joint happens by column. Value is delay from Write till Read

TABLE_OUTPUT - both column and row contains Write operations - so this is Write after Write (WaW) joint. Surprise - seems that Write operations are asynchronous and must be separated from previous Write with some delay

and finally TABLE_ANTI - in this case row is Read and column is Write. So this is Write after Read (WaR) joint. It's still unclear if this table applies to different instructions or it also can be applied to the same like

@P0 ISETP P0


How expensive to track all this joints

I added to ead.pl some statistics how many columns and rows can a single instruction have. Results depend on SM version and are unexpected in some ways:

• SM55 - avg 9.8 columns, 5 rows, HSETP2 has 17 (!) columns
• SM70 - avg 5.6 columns, 4.3 rows, CSMTEST has 8 columns and rows
  
• SM75 - avg 5.8 columns, 5.3 rows, PSETP has 9 rows
• SM90 - avg 6 columns, 5.8 rows, R2UR has 11 columns
  

So on average for each instruction we must track 1 Write and 3-4 Reads. I keep them (see file nv_track.h) in std::pair<const NV_tab *, int> - this is 12 bytes per record. All track records stored in std::list - so we have yet 2 pointers, total 28 bytes. Total size varies but in worst cases 15 (10 columns + 5 rows) * 28 = 420 bytes

Why this estimation is important? As you can see some tables while connecting require access to all encoded fields in their CONNECTOR CONDITIONS. So we have 2 variants

1. keep whole map of encoded fields and only 1 pointer to nv_instr for each instruction - then we could connect any joint at any moment
2. apply all connections for each instruction and keep only filtered by CONNECTOR CONDITIONS - then we could do their intersection on joint when it really happens
   

I chose the second option - connections are stored for every used register/predicate for each instruction in class reg_history and at joint I select only intersecting. Extracted fields have type std::unordered_map<std::string_view, uint64_t>, number of fields usually > 10 so size of this object at least 240 bytes + some memory for unordered_map itself

dg2.pl

So I wrote tool to optimize stall counts taking into account all 3 type of joints. The main change from dg.pl is function traverse_lat - it first builds array @rl of redundant stall counts, then apply restrictions for WaW and WaR and tries to reduce stall counts after that

I am too lazy to keep exact values for WaW so I used dirty hack - I never patch instruction for second Write. The explanation is simple - if we reduce stall count for first Write then there is enough delay, and if not then ptxas already inserted this delay between them

Complexity of this construction is O(N * log(N)) - I visit every instruction and also check possible WaRs/WaWs with couple of lookups in map

 

Config file

Most of time we are not interested in optimization of whole program - we want to optimize only hot loops where kernel spent most of its execution time. I could automatically identify only most nested loops by detecting backedge, Unfortunately, to detect all loops I need to do some inter-block analysis and this is not simple task. So I just shifted this responsibility to the user - you can select only some functions and even peek ranges inside function via external config file

 

Format of config file is very simple (see function read_config):

# this is comment
# process whole body of SomeFunction
.text.SomeFunction
# process loop in AnotherFunc from c0 till d40
.text.AnotherFunc c0-d40

As you can see I use dirty hack - in CUBIN files every function located in separate section with .text. prefix

You can generate skeleton of config for your CUBIN with dg2.pl -G option

 

How to build and install

despite the disheartening fact that tool is written on Perl all logic for instructions encoding/decoding/patching, latency/dependency tracking, ELF files parsing and so on implemented in C++ as XS modules. For reasons not entirely clear even to me, some modules are located in a separate repository. So first you need to build 3 modules from it:

1. Elf-Reader - to read/patch ELF files. I used dirty hack so that many other modules could reuse it via dynamic linking. For this reason it must be installed first
2. Cubin-Attrs for parsing/patching CUBIN attributes like EIATTR_KPARAM_INFO
3. Elf-FatBinary for extracting/replacing files in FatBinaries
   

Process of installing XS modules is always the same - run consequently

perl Makefile.PL
make
make test
sudo make install

Version of Perl is not important - mine is ancient 5.30. gcc/clang must support C++20

After this clone main denvdis repository. You need to make in test sub-directory smXXX.so for your specific architecture (make smxxx.so), libced.a and finally another XS module Cubin-Ced. Finally you must setup envvar SM_DIR to point on directory with smXXX.so modules, something like

cd test
export SM_DIR=`pwd`


That's all, now you can extract CUBIN files from your executable, run dg2.pl and so on - see how you can do it in single Makefile

 

dg2.pl command line options

Several are mandatory:

• -b to track read/write barriers
  
• -g to build CFG
• -l to use latency tables
• -t to track registers/predicates
  

Other options:

• -a - experimental option to apply optimization for all instructions (no check for Brt/BSSY/instructions with wait indices etc). Don't use it in production
• -C to peek config file
• -m to apply optimization for instructions with min wait attribute
• -P to really patch your CUBIN file. Make sure that you have backup or can easily recompile it
  

 

Results

As usual, the results depend on a number of factors, such as

• version of ptxas used for compilation (empirical observation - older versions can be optimized better)
• optimization flags used for compilation
• SM architecture
• complexity of code
  

and so on. I don't have expensive Blackwell GPU so tested on my own kernels for Pascal/Turing/Ampere. In worst cases we can reduce ~1% of stall counts for 1-1.5% of instructions

Average case 3% for 5-6% of instructions, and ever best results never exceeded 5% of total stall counts. It is necessary to take into account that some instructions belong to main calculation cycles so overall speed-up is not equivalent to the number of optimized stall counts

Anyway I think this is very good result to get 3-4% speed-up of kernels just by running one clumsy hand-made tool 

 

Possible further improvements

Since optimal instructions scheduling is classical combinatorial optimization we could employ standard solutions like pairwise permutations, three-element permutations and so on

I already described pairwise permutations here. In average this method can give speed-up in 3-4% but with greatly growing complexity of implementation

On other hand I am very skeptical about N-element permutations where N > 2. Simple justification - probability to find N mutually independent instructions (located not too far apart from each other) declines by exponent 

Inter-block analysis

Another way to reduce RaW joints is inter-block analysis. Currently all control flow instructions like CALL/JMP/JMX considered as joints for themself and because we don't know which register/predicate will be used in another block - they also break all chains (see how they complete chain marking with function fill_rl_till)

One possible solution would be to track using registers/predicates in referred blocks and continue wait chains till those instructions. However it's hard to estimate what gain it could give

Avoiding fake joints

Finally there are also fake WaR/WaW joints. Lets observe couple of adjacent instructions:
@P0 IMAD R1, ...
!@P0 IMAD R1, ...


In this simple example, it is obvious that this is not WaW joint for register R1. If we could somehow prove that such pairs of instructions always executed by disjoint sets of threads we could remove these joints. Unfortunately such proof is equivalent to famous "halting problem" and in general cannot be solved in polynomial time. Anyway I add to dg2 config file couple of options to manually eliminate similar fake joints:

• to remove WaR -war list-of-ranges
• to remove WaW -waw list-of-ranges 

See function read_config for details