# GPU-accelerated Auxiliary-field quantum Monte Carlo with multi-Slater
determinant trial states

Yifei Huang<EMAIL_ADDRESS>ByteDance Research, Zhonghang Plaza,
No. 43, North 3rd Ring West Road, Haidian District, Beijing 100089, China
Zhen Guo  ByteDance Research, Zhonghang Plaza, No. 43, North 3rd Ring West
Road, Haidian District, Beijing 100089, China  Hung Q. Pham  ByteDance
Research, San Jose, CA 95110, US.  Dingshun Lv<EMAIL_ADDRESS>ByteDance Research, Zhonghang Plaza, No. 43, North 3rd Ring West Road, Haidian
District, Beijing 100089, China

###### Abstract

The accuracy of phaseless auxiliary-field quantum Monte Carlo (ph-AFQMC) can
be systematically improved with better trial states. Using multi-Slater
determinant trial states, ph-AFQMC has the potential to faithfully treat
strongly correlated systems, while balancing the static and dynamical
correlations on an equal footing. This preprint presents an implementation and
application of graphics processing unit-accelerated ph-AFQMC, for multi-Slater
determinant trial wavefunctions (GPU-accelerated MSD-AFQMC), to enable
efficient simulation of large-scale, strongly correlated systems. This
approach allows for nearly-exact computation of ground state energies in
multi-reference systems. Our GPU-accelerated MSD-AFQMC is implemented in the
open-source code ipie, a Python-based AFQMC package [J. Chem. Theory Comput.,
2022, 19(1): 109-121]. We benchmark the performance of the GPU code on
transition-metal clusters like [Cu2O2]2+ and [Fe2S2(SCH3)]2-. The GPU code
achieves at least sixfold speedup in both cases, comparing the timings of a
single A100 GPU to that of a 32-CPU node. For [Fe2S2(SCH3)]2-, we demonstrate
that our GPU MSD-AFQMC can recover the dynamical correlation necessary for
chemical accuracy with an MSD trial, despite the large number of determinants
required ($>10^{5}$). Our work significantly enhances the efficiency of MSD-
AFQMC calculations for large, strongly correlated molecules by utilizing GPUs,
offering a promising path for exploring the electronic structure of transition
metal complexes.

##  I Introduction

Auxiliary-field quantum Monte Carlo (AFQMC) Zhang, Carlson, and Gubernatis
(1995); Zhang and Krakauer (2003) has gained increasing popularity in quantum
chemistry Lee, Pham, and Reichman (2022); Motta and Zhang (2018) and is also
recognized as a powerful approach within the realm of quantum algorithms
Huggins  _et al._ (2022); Wan  _et al._ (2023); Amsler  _et al._ (2023); Kiser
_et al._ (2023); Huang  _et al._ (2024). AFQMC with phaseless approximation
(ph-AFQMC) imposes constraints on the evolution paths of walkers, thereby
suppressing the sign problem while introducing biases associated with the
trial states. As the quality of the trial states improves, one can
systematically reduce the biases in AFQMC calculations. The gold standard
method of quantum chemistry, coupled cluster singles and doubles with
perturbative triples (CCSD(T)), is known to struggle in achieving chemical
accuracy for ab initio systems with multi-reference characteristics, including
bond dissociation and transition metal complexes. The accuracy of AFQMC with
single-determinant trial states (SD-AFQMC) performs even worse than the
(CCSD(T)) results for these systems Lee, Pham, and Reichman (2022). By
employing more sophisticated trial states with multi-Slater determinants (MSD-
AFQMC), the accuracy of AFQMC has been shown to approach the exact results for
several benchmark multi-reference systems. More specifically, the accuracy of
MSD-AFQMC is on par with the multi-reference configuration interaction with
Davidson correction (MRCI+Q) method, while having a better scaling and can be
extended to larger systems Lee, Pham, and Reichman (2022). These benchmarks
positions MSD-AFQMC as one of the front-runners for large-scale calculations
of multi-reference systems, where static and dynamic correlations need to
addressed on an equal footing Shee  _et al._ (2023).

ipie is a Python-based AFQMC code that was optimized for high-performance
computing on central processing units (CPUs), with a focus on simplicity and
speed. It integrates Numba’s JIT compilation to enhance the computational
efficiency of specific kernels and uses MPI parallelism for effective
distributed computing. While engineering efforts were directed towards GPUs
for single-Slater determinant trials (SD-AFQMC), the MSD-AFQMC code has only
been implemented on general-purpose CPUs due to the complicated excitations in
multi-determinant trial states. This underscores the pressing need for MSD-GPU
development to advance large-scale calculations for transition metal systems.
In this preprint, we present our GPU implementation and benchmarking of MSD-
AFQMC as an important extended feature of ipie. We implemented Nvidia Compute
Unified Device Architecture (CUDA) kernel functions with a cupy interface to
facilitate parallel treatments of the different excitations in the MSD trials
within ipie.

##  II Theory

###  II.1 Phaseless AFQMC

AFQMC is a projector quantum Monte Carlo method that realises the imaginary
time evolution (ITE):

$\left|\Psi_{0}\right\rangle\propto\lim_{\tau\rightarrow\infty}\exp(-\tau\hat{H})\left|\Phi_{0}\right\rangle=\lim_{n\rightarrow\infty}(\exp(-\tau\hat{H}/n))^{n}|\Phi_{0}\rangle,$
(1)

where $\left|\Psi_{0}\right\rangle$ is the ground state wavefunction, and
$\left|\Phi_{0}\right\rangle$ is an initial state that have a non-zero overlap
with the ground state. We pivot our GPU engineering to ab initio Hamiltonian,
which, in second quantization, is given by

$\hat{H}=\sum_{p,q=1}^{N}h_{pq}\hat{a}_{p}^{\dagger}\hat{a}_{q}+\frac{1}{2}\sum_{p,q,r,s=1}^{N}g_{psqr}\hat{a}_{p}^{\dagger}\hat{a}_{q}^{\dagger}\hat{a}_{r}\hat{a}_{s}.$
(2)

where $h_{pq}$ and $g_{pqrs}$ are the 1-electron and 2-electron repulsion
integrals (ERI). This can be rewritten as

$\hat{H}=\sum_{p,q=1}^{N}h^{\prime}_{pq}\hat{a}_{p}^{\dagger}\hat{a}_{q}+\frac{1}{2}\sum_{\gamma=1}^{N_{\gamma}}\left(\sum_{pq}L_{pq}^{\gamma}\hat{a}_{p}^{\dagger}\hat{a}_{q}\right)^{2}$
(3)

using the Cholesky decomposition to the two-electron repulsion integral (ERI).
Here, we have the

$h^{\prime}_{pq}=h_{pq}-\frac{1}{2}\sum_{r}(pr|rq)$ (4)

Applying the Hubbard–Stratonovich transformation to the two-body termHubbard
(1959); Stratonovich (1958), the effective propagator contains only one-body
operators,

$e^{-\Delta\tau\hat{H}}=\int\mathrm{d}\mathbf{x}\
p(\mathbf{x})\hat{B}(\mathbf{x})+\mathcal{O}\left(\Delta\tau^{2}\right),$ (5)

where $p(\mathbf{x})$ is the standard Gaussian distribution,
$\textbf{x}=(x_{1},x_{2},\cdots,x_{N_{\gamma}})$ are the auxiliary fields, and
$\hat{B}$ is a propagator with only one-body terms on its exponents. Here, we
have introduced the first-order Trotter decomposition, and therefore, the
$\mathcal{O}\left(\Delta\tau^{2}\right)$ Trotter error term.

In AFQMC, each walker is a single Slater determinant, which samples auxiliary
fields $\mathbf{x}_{i}$ and becomes another single Slater determinant due to
the Thouless’ theorem:
$B(\mathbf{x}_{i})\ket{\phi_{i}(\tau)}=\ket{\phi_{i}(\tau+\Delta\tau)}$. Each
walker represents a statistical sample of the global wavefunction at imaginary
time $\tau$, written as

$|\Psi(\tau)\rangle=\sum_{i}^{N_{\textrm{w}}}w_{i}(\tau)\frac{\left|\phi_{i}(\tau)\right\rangle}{\left\langle\Psi_{T}|\phi_{i}(\tau)\right\rangle},$
(6)

where $w_{i}(\tau)$ is the weight, $|\phi_{i}(\tau)\rangle$ is the
wavefunction of the $i$-th walker at time $\tau$ and $|\Psi_{T}\rangle$ is the
trial wavefunction used for importance sampling.

We dynamically shift the distribution of auxiliary fields using the force bias
$\overline{\mathbf{x}}_{i}$ defined by

$\overline{x}_{\gamma}(\Delta\tau,\tau)=-\sqrt{\Delta\tau}\frac{\left\langle\Psi_{T}\left|\sum_{pq}L_{pq}^{\gamma}\hat{a}_{p}^{\dagger}\hat{a}_{q}\right|\psi_{i}(\tau)\right\rangle}{\left\langle\Psi_{T}|\psi_{i}(\tau)\right\rangle}.$
(7)

At each imaginary time step, the overlap ratio of the $i$-th walker is

$S_{i}(\tau,\Delta\tau)=\frac{\left\langle\Psi_{\textrm{T}}\left|\hat{B}\left(\Delta\tau,\mathbf{x}_{i}-\overline{\mathbf{x}}_{i}\right)\right|\psi_{i}(\tau)\right\rangle}{\left\langle\Psi_{\textrm{T}}|\psi_{i}(\tau)\right\rangle},$
(8)

with the phase of the overlap as

$\theta_{i}(\tau)=\arg\left[S_{i}(\tau,\Delta\tau)\right].$ (9)

Hence, we can define the importance function for the update of the weights
$w_{i}(\tau)$s:

$I\left(\mathbf{x}_{i},\overline{\mathbf{x}}_{i},\tau,\Delta\tau\right)=S_{i}(\tau,\Delta\tau)e^{\mathbf{x}_{i}\cdot\overline{\mathbf{x}}_{i}-\overline{\mathbf{x}}_{i}\cdot\overline{\mathbf{x}}_{i}/2},$
(10)

The phase factor in Eq. 9 can range from 0 to $2\pi$ and therefore causes the
phase/sign problem. In order to control this phase/sign problem, the phaseless
approximation Zhang and Krakauer (2003) is applied during the update of the
weights $w_{i}(\tau)$:

$w_{i}(\tau+\Delta\tau)=I_{\mathrm{ph}}\left(\mathbf{x}_{i},\overline{\mathbf{x}}_{i},\tau,\Delta\tau\right)\times
w_{i}(\tau).$ (11)

where $I_{ph}$ is given by

$I_{\mathrm{ph}}\left(\mathbf{x}_{i},\overline{\mathbf{x}}_{i},\tau,\Delta\tau\right)=\left|I\left(\mathbf{x}_{i},\overline{\mathbf{x}}_{i},\tau,\Delta\tau\right)\right|\times\max\left[0,\cos\left(\theta_{i}(\tau)\right)\right],$
(12)

which remains real and positive throughout the propagation.

When the trial wavefunction is a single Slater determinant, the overlaps at
each time step is simply the overlap between two Slater determinants:

$\langle\Psi_{T}|{\phi_{i}}\rangle=\text{det}\left(\Psi_{T}^{\dagger}\phi_{i}\right)$
(13)

where $\Psi_{T}$ and $\phi_{i}$ are the matrix representation of the two
Slater determinants. The Green’s function, i.e., the one-body reduced density
matrix (1-RDM) in a mixed form is computed as follows:

$G_{ij}=\frac{\bra{\Psi_{T}}a_{i}^{\dagger}a_{j}\ket{\phi_{i}}}{\langle{\Psi_{T}}|{\phi_{i}}\rangle}=\left[\phi_{i}\left(\Psi_{T}^{\dagger}\phi_{i}\right]^{-1}\Psi_{T}^{\dagger}\right]$
(14)

The two-body RDMs (2-RDMs) can be obtained from the 1-RDM using the
generalized Wicks theorem Wick (1950); Balian and Brezin (1969). The mixed
energy estimation can therefore, be calculated by the 1-RDMs and 2-RDMs.

For SD-AFQMC, the only calculations needed are matrix multiplications, as
shown above. This makes it fairly straightforward for GPU implementation, with
the $N_{w}$ dimension also batched for parallelization.

###  II.2 Multi-Slater determinant AFQMC

The trial wavefunction in this case is written as a linear combination of
different Slater determinants:

$\ket{\Psi_{T}}=\sum_{j=1}^{N_{d}}c_{j}\ket{\phi_{j}},$ (15)

where $N_{d}$ is the number of determinants in the trial. The Slater
determinants can be either a configuration interaction (CI) expansion, where
the determinants are orthogonal to each other under the same set of orbitals,
or non-orthogonal under different sets of orbitals Landinez Borda, Gomez, and
Morales (2019). In this preprint, we only work with the former case where each
determinant is represented as a configuration.

The naive approach to implementing MSD-AFQMC involves performing SD-AFQMC for
each individual determinant in the trial wavefunction. Although this makes GPU
parallelization straightforward, it is inefficient because the orbitals used
in the CI expansion are the same across determinants. Starting from scratch
for each determinant results in linear time scaling with respect to $N_{d}$.
Moreover, fully parallelizing this on GPUs would lead to a linear increase in
memory usage with $N_{d}$, which is not scalable. In contrast, the ipie
implementation of MSD-AFQMC achieves sub-linear scaling in $N_{d}$ by reusing
orbital information Shi and Zhang (2021). This advanced implementation
demonstrates that the time required for MSD-AFQMC with 2 determinants is
nearly the same as with 1000 determinants. However, this efficiency
complicates GPU implementation, as the trial wavefunction must be managed
carefully to optimize memory usage.

Meanwhile, ipie integrates external quantum chemistry packages to facilitate a
convenient workflow for MSD-AFQMC. For more complicated trial wavefunctions,
such as multiple Slater determinant (MSD) trials derived from selected
configuration interaction (SCI), interfaces with PySCF Sun  _et al._ (2018)
(shciscf interface), Dice Holmes, Tubman, and Umrigar (2016); Sharma  _et al._
(2017), and TrexIOPosenitskiy  _et al._ (2023) are available and easy to use.
In this preprint, we use Dice to perform the SCI calculations.

##  III GPU-accelerated MSD-AFQMC and timing benchmarks

ph-AFQMC with MSD trials is useful for multi-reference systems where free-
projection is not feasible due to the sign problem. In this main section, we
report our GPU-accelerated MSD-AFQMC workflow based on Wick’s theorem Mahajan,
Lee, and Sharma (2022) . We used cupy.einsum as implemented through the
cuTENSOR library to accelerate matrix multiplications. Furthermore, we
implemented Wick’s algorithm entirely on the GPU with CUDA kernels. These
kernels substantially accelerated computational hotspots in MSD-AFQMC, namely
calculations of the Green’s function, overlap, and local energy. One only need
minimal changes to the ipie multi-determinant example to make use of the GPU
code:

⬇

1%env CUPY_ACCELERATORS=cutensor # for notebook, for .py you can set this in
terminal

2

3import cupy

4

5from ipie.config import config

6

7config.update_option("use_gpu", True)

8

9import h5py

10import numpy

11from pyscf import fci, gto, mcscf, scf

12

13from ipie.hamiltonians.generic import Generic as HamGeneric

14from ipie.qmc.afqmc import AFQMC

15from ipie.systems.generic import Generic

16from ipie.trial_wavefunction.particle_hole import ParticleHole

17from ipie.utils.from_pyscf import gen_ipie_input_from_pyscf_chk

18

19nocca = 4

20noccb = 2

21

22mol = gto.M(

23atom=[("N", 0, 0, 0), ("N", (0, 0, 3.0))],

24basis="ccpvdz",

25verbose=3,

26spin=nocca - noccb,

27unit="Bohr",

28)

29mf = scf.RHF(mol)

30mf.chkfile = "scf.chk"

31ehf = mf.kernel()

32M = 6

33N = 6

34mc = mcscf.CASSCF(mf, M, N)

35mc.chkfile = "scf.chk"

36e_tot, e_cas, fcivec, mo, mo_energy = mc.kernel()

37coeff, occa, occb = zip(

38*fci.addons.large_ci(fcivec, M, (nocca, noccb), tol=1e-8, return_strs=False)

39)

40

41with h5py.File("scf.chk", "r+") as fh5:

42 fh5["mcscf/ci_coeffs"] = coeff

43 fh5["mcscf/occs_alpha"] = occa

44 fh5["mcscf/occs_beta"] = occb

45

46gen_ipie_input_from_pyscf_chk("scf.chk", mcscf=True)

47mol_nelec = [8, 6]

48

49with h5py.File("hamiltonian.h5") as fa:

50chol = fa["LXmn"][()]

51h1e = fa["hcore"][()]

52e0 = fa["e0"][()]

53

54num_basis = chol.shape[1]

55system = Generic(nelec=mol_nelec)

56

57num_chol = chol.shape[0]

58ham = HamGeneric(

59numpy.array([h1e, h1e]),

60chol.transpose((1, 2, 0)).reshape((num_basis * num_basis, num_chol)),

61e0,

62)

63

64with h5py.File("wavefunction.h5", "r") as fh5:

65 coeff = fh5["ci_coeffs"][:]

66 occa = fh5["occ_alpha"][:]

67 occb = fh5["occ_beta"][:]

68wavefunction = (coeff, occa, occb)

69trial = ParticleHole(

70 wavefunction,

71 mol_nelec,

72 num_basis,

73 num_dets_for_props=len(wavefunction[0]),

74 verbose=True,

75)

76trial.compute_trial_energy = True

77trial.build()

78trial.half_rotate(ham)

79

80afqmc_msd = AFQMC.build(

81 mol_nelec,

82 ham,

83 trial,

84 num_walkers=10,

85 num_steps_per_block=25,

86 num_blocks=10,

87 timestep=0.005,

88 stabilize_freq=5,

89 seed=96264512,

90 pop_control_freq=5,

91 verbose=True,

92)

93afqmc_msd.run()

94afqmc_msd.finalise(verbose=True)

Code Snippet 1: Code snippet for MSD calculation with a single GPU.

Here one simply needs to set the cutensor environment variable, use the GPU
config and make sure the ParticleHole class is used for the trial
wavefunction.

###  III.1 Implementation

In MSD-AFQMC, the trial wavefunction comprises various configurations arising
from different excitations relative to the reference configuration,
complicating GPU parallelization.

In ipie, the Wick’s theorem calculations are organized into four functional
sets: get_dets, reduce_CI, fill_os, and get_ss, where ss and os refer to same-
spin and opposite-spin, respectively. Each set handles single, double, triple,
and n-fold excitation components. Specifically, get_dets aids in overlap
calculations, reduce_CI is crucial for evaluating Green’s functions, and the
last two sets, fill_os and get_ss, contribute to the mixed energy estimator.

Our implementation primarily involves element-wise and reduction operations,
with meticulous management of various dimensions to balance time and memory
usage. Readers interested in more detailed information about the
implementation are encouraged to consult the Appendix.

###  III.2 Benchmark results

We benchmark our MSD-AFQMC GPU implementation against the previous CPU version
using the [Cu2O2]2+ system with the structural parameter $f=0$!Mahajan and
Sharma (2021) as described in the earlier ipie release paper Malone  _et al._
(2022). We adopt the same BS1 basis used in 21 and the correlation space
contains (32e, 108o) after a frozen core. To ensure a direct comparison, we
employ a total of 10 walkers, the same as the configuration used in the
reference benchmark Malone  _et al._ (2022). Additionally, we conduct tests
with 640 walkers to provide a more realistic evaluation. Consistent with
earlier benchmarks, we define a block as 25 propagation steps, incorporating
one local energy estimation and executing population control every 5 steps.

With 10 walkers, we find that our GPU implementation on a single NVIDIA A100
card is six times faster than the CPU version on a single CPU core when the
number of determinants in the trial is less than $10^{3}$. The speedup
increases to tenfold with $10^{4}$ determinants and about 100-fold with
$10^{6}$ determinants (see Fig. 1(a)). This is expected as the GPU utility
rate increases with more determinants in the trial. This scenario is
particularly relevant when we have many determinants but a small number of
walkers (i.e., 10) in each MPI process.

With 640 walkers, we compare the performance of our GPU code on a single A100
card against our CPU implementation on 32 CPU cores, reflecting typical
production-level AFQMC calculations. As depicted in Fig. 1 (b), we observe a
fourfold speedup with fewer than $10^{2}$ determinants, which increases to
approximately sixfold as the number of determinants grows. To tackle a larger
number of determinants within the memory constraints, we partition the
determinants into chunks and compute each chunk sequentially. This partition
introduces overhead that primarily impacts the energy estimator. For instance,
with $10^{3}$ determinants, the estimator accounts for less than 50% of the
total block time (0.38s on average out of 0.91s); with $10^{6}$ determinants,
this ratio increases to 75% (37s out of 49s). A different approach for
computing local energy may be required for systems that necessitate numerous
determinants in the MSD trial.

Figure 1: (a) Comparison of time per MSD-AFQMC block with 10 walkers on a
single CPU core and a single A100 GPU. The system we considered was [Cu2O2]2+
using the BS1 basis Mahajan, Lee, and Sharma (2022), which was also a CPU time
benchmark example in the original ipie release Malone  _et al._ (2022). (b)
Time per block with 640 walkers on a single A100 against 32 CPU cores.

The iron-sulfur clusters is known for its notoriously strong correlation due
to the large number of d-orbital electrons in iron and the double exchange
mechanism together with the sulfur p-orbital electrons Sharma  _et al._
(2014); Li  _et al._ (2019). Here we performed timing and absolute energy
benchmarks on the (20o, 30e) active space of the [Fe2S2(SCH3)]2- cluster. The
active space and integrals were obtained from Refs. 24 and 26. In Fig. 2(a),
one can see that in contrast to the 108-orbital calculation of [Cu2O2]2+, we
only have a twofold speedup using a single A100 card compared to 32 CPUs. This
speedup increases to almost tenfold when the number of determinants exceeds
$10^{4}$.

For absolute energies, we compute the reference energy from full configuration
interaction (FCI) and use two sets of orbitals for this benchmark. The first
set consists of natural orbitals obtained by diagonalizing the 1-electron
reduced density matrix (1-RDM) from a high-level wavefunction Lee  _et al._
(2023). Performing MSD-AFQMC calculations based on these orbitals, we can
reach within chemical accuracy from the FCI result with around $3\times
10^{5}$ determinants in the trial. On the other hand, reaching chemical
accuracy is more challenging when we use localized orbitals from atomic
orbitals. As shown in Fig. 2(b), the difference from the reference value is
still 4mHa with more than $2.5\times 10^{6}$ determinants. These observations
indicate the importance of choosing a proper set of orbitals for calculations
on strongly correlated systems. Here we cheated a little bit using natural
orbitals resulted from a near-exact DMRG calculation, which is not viable for
larger systems. However, we remark that we can always perform calculations
with lower bond dimensions (DMRG) or larger thresholds (SCI) and obtain the
natural orbitals thereafter. Another interesting point about the mixed energy
estimator is that the energies derived using localized orbitals with a limited
number of determinants are lower than the FCI energy and approach upwards
toward the FCI reference.

Figure 2: Timing and absolute energy benchmarks on the [Fe2S2(SCH3)]2-
cluster. (a) Comparison of time per MSD-AFQMC block with 640 walkers on 32 CPU
cores and a single A100 GPU. (b) Absolute energies derived using localized
atomic orbitals and natural orbitals. The full configuration interaction
result is used as reference.

##  IV Conclusions and outlooks

In this preprint, we present an efficient and user-friendly GPU implementation
of MSD-AFQMC, which we believe will serve as a valuable tool for both
methodology developers and electronic structure practitioners aiming to
perform large-scale calculations on multi-reference systems. These systems
require a balanced treatment of both static and dynamic correlations for
accurate descriptions. On the other hand, as one can view AFQMC as a tool to
make up for dynamical correlation beyond the active space, our [Fe2S2(SCH3)]2-
benchmark, together with the previous [Cu2O2]2+ results Malone  _et al._
(2022), indicate that MSD-AFQMC may be even a faithful alternative to
exhaustive methods within the active space. Moreover, considering recent
proposals for preparing AFQMC trials on quantum devices, this new feature may
also attract interest from researchers working with quantum trials which
typically involve numerous determinants Huggins  _et al._ (2022).

We note that our implementation is still in its early stages and runs on a
single GPU only. We expect it being straightforward to extend our Wick’s
theorem calculations to a multi-GPU setup, enabling the calculation of larger
systems. Additionally, since evaluating properties other than ground-state
energy is crucial, incorporating the auto-differentiation method into our GPU-
MSD framework would be highly beneficial and of great interest to the
community.

As demonstrated in our [Fe2S2(SCH3)]2- benchmark, a substantial number of
determinants may be required to accurately account for the dynamical
correlation in these strongly correlated systems. Addressing dynamical
correlation for larger iron-sulfur clusters could become intractable Sharma
_et al._ (2014); Li  _et al._ (2019). It would be interesting to explore
whether a GPU implementation of MPS-AFQMC (AFQMC with matrix product state
trials) could treat these systems more effectively Wouters  _et al._ (2014);
Qin (2020); Jiang  _et al._ (2024).

##  V Acknowledgements

This concise preprint introduces a significant enhancement to the ipie package
and complements an incoming ipie release paper. In the future, as more GPU-MSD
features are developed, they will be incorporated into this document. The
authors would like to thank Joonho Lee and Tong Jiang for their valuable
discussions on the benchmarks. Additionally, YH and DL express gratitude to
Jerry Chen from Nvidia for his suggestion on the use of cooperative groups.

##  VI Author contributions

YH and DL implemented the GPU code with assistance from JG. YH conducted the
benchmark calculations with support from HP.

##  Appendix A Implementation details

For get_dets, the output arrays have dimensions ($N_{w}$, $N_{d}$). Hence, we
can rewrite the for loops in these axes as element-wise kernels that contain
$N_{w}\cdot N_{d}$ threads in total. For fill_os, we still only need element-
wise kernels, the only difference from get_dets is the output arrays have
three dimensions: $N_{w}$, $N_{d}$ and $N_{\gamma}$. Therefore we have one
more dimension to parallelize. In build_det_matrix and build_cofactor_matrix
functions, we can further parallelize the $N_{exct}$ dimensions, which
represents the order of excitation. For get_ss, the $N_{w}$ and $N_{d}$
dimensions can still be parallelized but reduce operations are needed in the
$N_{\gamma}$ dimension. So we add a serial for-loop inside each thread. The
serial reduction operation can be accelerated by cooperative groups in CUDA.

The most tricky one is the reduce_CI part. In this set of functions, we are
updating the walkers.CIs with dimensions ($N_{w}$, $N_{acto}$, $N_{acte}$),
where the last two dimensions denotes the number of active-space orbitals and
electrons. However, we update them according to an array with dimensions
($N_{w}$, $N_{d}$). This mismatch results in a situation where different
determinants from the trial contribute to the same walkers.CI element. In
other words, we run into ”collisions” when we try to add upon the values of
the walkers.CI entries from each determinant. We use atomicAdd to resolve this
problem, which performs the read, add and write operation in a single atomic
operation without interference from other threads.

For all of the n-fold excitation functions, a cupy.linalg.det operation is
needed but can’t be wrapped into a CUDA kernel. We dig this determinant
calculation out of the for loops, compute them once for all indices of
$N_{exct}$, $N_{w}$, $N_{d}$ and send the results into the kernels. In
build_det_matrix and build_cofactor_matrix functions, we can further
parallelize the $N_{exct}$ dimensions.

## References

  * Zhang, Carlson, and Gubernatis (1995) S. Zhang, J. Carlson, and J. E. Gubernatis, “Constrained Path Quantum Monte Carlo Method for Fermion Ground States,” Phys. Rev. Lett. 74, 3652–3655 (1995).
  * Zhang and Krakauer (2003) S. Zhang and H. Krakauer, “Quantum Monte Carlo Method using Phase-Free Random Walks with Slater Determinants,” Phys. Rev. Lett. 90, 136401 (2003).
  * Lee, Pham, and Reichman (2022) J. Lee, H. Q. Pham, and D. R. Reichman, “Twenty Years of Auxiliary-Field Quantum Monte Carlo in Quantum Chemistry: An Overview and Assessment on Main Group Chemistry and Bond-Breaking,” J. Chem. Theory Comput. 18, 7024–7042 (2022).
  * Motta and Zhang (2018) M. Motta and S. Zhang, “Ab initio computations of molecular systems by the auxiliary-field quantum Monte Carlo method,” WIREs Computational Molecular Science 8, e1364 (2018).
  * Huggins  _et al._ (2022) W. J. Huggins, B. A. O’Gorman, N. C. Rubin, D. R. Reichman, R. Babbush, and J. Lee, “Unbiasing fermionic quantum Monte Carlo with a quantum computer,” Nature 603, 416–420 (2022).
  * Wan  _et al._ (2023) K. Wan, W. J. Huggins, J. Lee, and R. Babbush, “Matchgate shadows for fermionic quantum simulation,” Commun. Math. Phys 404, 629–700 (2023).
  * Amsler  _et al._ (2023) M. Amsler, P. Deglmann, M. Degroote, M. P. Kaicher, M. Kiser, M. Kühn, C. Kumar, A. Maier, G. Samsonidze, A. Schroeder, _et al._ , “Classical and quantum trial wave functions in auxiliary-field quantum monte carlo applied to oxygen allotropes and a cubr2 model system,” J. Chem. Phys. 159 (2023).
  * Kiser  _et al._ (2023) M. Kiser, A. Schroeder, G.-L. R. Anselmetti, C. Kumar, N. Moll, M. Streif, and D. Vodola, “Classical and quantum cost of measurement strategies for quantum-enhanced auxiliary field quantum monte carlo,” New J. Phys. (2023).
  * Huang  _et al._ (2024) B. Huang, Y.-T. Chen, B. Gupt, M. Suchara, A. Tran, S. McArdle, and G. Galli, “Evaluating a quantum-classical quantum Monte Carlo algorithm with Matchgate shadows,” arXiv (2024), 2404.18303 .
  * Shee  _et al._ (2023) J. Shee, J. L. Weber, D. R. Reichman, R. A. Friesner, and S. Zhang, “On the potentially transformative role of auxiliary-field quantum monte carlo in quantum chemistry: A highly accurate method for transition metals and beyond,” J. Chem. Phys. 158 (2023).
  * Hubbard (1959) J. Hubbard, “Calculation of partition functions,” Phys. Rev. Lett. 3, 77 (1959).
  * Stratonovich (1958) R. Stratonovich, Sov. Phys. Dokl. 2, 416 (1958).
  * Wick (1950) G.-C. Wick, “The evaluation of the collision matrix,” Physical review 80, 268 (1950).
  * Balian and Brezin (1969) R. Balian and E. Brezin, “Nonunitary bogoliubov transformations and extension of wick’s theorem,” Il Nuovo Cimento B (1965-1970) 64, 37–55 (1969).
  * Landinez Borda, Gomez, and Morales (2019) E. J. Landinez Borda, J. Gomez, and M. A. Morales, “Non-orthogonal multi-Slater determinant expansions in auxiliary field quantum Monte Carlo,” J. Chem. Phys. 150, 074105 (2019).
  * Shi and Zhang (2021) H. Shi and S. Zhang, “Some recent developments in auxiliary-field quantum monte carlo for real materials,” The Journal of chemical physics 154 (2021).
  * Sun  _et al._ (2018) Q. Sun, T. C. Berkelbach, N. S. Blunt, G. H. Booth, S. Guo, Z. Li, J. Liu, J. D. McClain, E. R. Sayfutyarova, S. Sharma, _et al._ , “Pyscf: the python-based simulations of chemistry framework,” Wiley Interdiscip Rev Comput Mol Sci 8, e1340 (2018).
  * Holmes, Tubman, and Umrigar (2016) A. A. Holmes, N. M. Tubman, and C. Umrigar, “Heat-bath configuration interaction: An efficient selected configuration interaction algorithm inspired by heat-bath sampling,” J. Chem. Theory Comput. 12, 3674–3680 (2016).
  * Sharma  _et al._ (2017) S. Sharma, A. A. Holmes, G. Jeanmairet, A. Alavi, and C. J. Umrigar, “Semistochastic heat-bath configuration interaction method: Selected configuration interaction with semistochastic perturbation theory,” J. Chem. Theory Comput. 13, 1595–1604 (2017).
  * Posenitskiy  _et al._ (2023) E. Posenitskiy, V. G. Chilkuri, A. Ammar, M. Hapka, K. Pernal, R. Shinde, E. J. Landinez Borda, C. Filippi, K. Nakano, O. Kohulák, S. Sorella, P. de Oliveira Castro, W. Jalby, P. L. Ríos, A. Alavi, and A. Scemama, “TREXIO: A file format and library for quantum chemistry,” J. Chem. Phys. 158 (2023), 10.1063/5.0148161, 174801.
  * Mahajan, Lee, and Sharma (2022) A. Mahajan, J. Lee, and S. Sharma, “Selected configuration interaction wave functions in phaseless auxiliary field quantum monte carlo,” J. Chem. Phys. 156 (2022), https://doi.org/10.1063/5.0087047.
  * Mahajan and Sharma (2021) A. Mahajan and S. Sharma, “Taming the sign problem in auxiliary-field quantum monte carlo using accurate wave functions,” J. Chem. Theory Comput. 17, 4786–4798 (2021).
  * Malone  _et al._ (2022) F. D. Malone, A. Mahajan, J. S. Spencer, and J. Lee, “Ipie: A python-based auxiliary-field quantum monte carlo program with flexibility and efficiency on cpus and gpus,” J. Chem. Theory Comput. 19, 109–121 (2022).
  * Sharma  _et al._ (2014) S. Sharma, K. Sivalingam, F. Neese, and G. K.-L. Chan, “Low-energy spectrum of iron–sulfur clusters directly from many-particle quantum mechanics,” Nat. Chem. 6, 927–933 (2014).
  * Li  _et al._ (2019) Z. Li, S. Guo, Q. Sun, and G. K.-L. Chan, “Electronic landscape of the p-cluster of nitrogenase as revealed through many-electron quantum wavefunction simulations,” Nature chemistry 11, 1026–1033 (2019).
  * Li and Chan (2017) Z. Li and G. K.-L. Chan, “Spin-projected matrix product states: Versatile tool for strongly correlated systems,” J. Chem. Theory Comput. 13, 2681–2695 (2017).
  * Lee  _et al._ (2023) S. Lee, J. Lee, H. Zhai, Y. Tong, A. M. Dalzell, A. Kumar, P. Helms, J. Gray, Z.-H. Cui, W. Liu, _et al._ , “Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry,” Nature communications 14, 1952 (2023).
  * Wouters  _et al._ (2014) S. Wouters, B. Verstichel, D. Van Neck, and G. K.-L. Chan, “Projector quantum monte carlo with matrix product states,” Physical Review B 90, 045104 (2014).
  * Qin (2020) M. Qin, “Combination of tensor network states and green’s function monte carlo,” Physical Review B 102, 125143 (2020).
  * Jiang  _et al._ (2024) T. Jiang, B. O’Gorman, A. Mahajan, and J. Lee, “Unbiasing fermionic auxiliary-field quantum monte carlo with matrix product state trial wavefunctions,” arXiv preprint arXiv:2405.05440 (2024).


# An Automated Testing and Debugging Toolkit for Gate-Level Logic Synthesis
Applications

Siang-Yun Lee  LSI, EPFLSwitzerland ,  Heinz Riener  Cadence Design
SystemsGermany and  Giovanni De Micheli  LSI, EPFLSwitzerland

###### Abstract.

Correctness and robustness are essential for logic synthesis applications, but
they are often only tested with a limited set of benchmarks. Moreover, when
the application fails on a large benchmark, the debugging process may be
tedious and time-consuming. In some fields such as compiler construction,
automatic testing and debugging tools are well-developed to support developers
and provide minimal guarantees on program quality. In this paper, we adapt
fuzz testing and delta debugging techniques and specialize them for gate-level
netlists commonly used in logic synthesis. Our toolkit improves over similar
tools specialized for the AIGER format by supporting other gate-level netlist
formats and by allowing a tight integration to provide $10\times$ speed-up.
Experimental results show that our fuzzer captures defects in mockturtle, ABC,
and LSOracle with $10\times$ smaller testcases and our testcase minimizer
extracts minimal failure-inducing cores using $2\times$ fewer oracle calls.

††conference: ; July 18-21, 2022; Virtual Conference

##  1\. Introduction

Logic synthesis is the task of turning an abstract specification into a gate-
level netlist composed of logic gates while considering cost functions for
area, delay, and power. Logic synthesis plays a crucial role in modern
microchip design flows. Sophisticated algorithmic solutions are readily
available as open-sourced libraries and tools (Soeken et al., 2018; Brayton
and Mishchenko, 2010; Neto et al., 2019). These algorithms can optimize
netlists with millions of gates within only a few seconds, relying on bit-
precise reasoning engines. The inherent complexity of these engines, optimized
for many corner cases, makes logic synthesis algorithms susceptible to design
and implementation errors. Moreover, algorithms are often only tested on fixed
benchmark suites, such as the EPFL logic synthesis benchmarks (Amarú et al.,
2015). Due to numerous possibilities to implement the same Boolean function
with different circuit structures, it is not rare that subtle faults slip
through the development process and only show themselves when the algorithm is
used in practice.

Motivated by the success of automated testing methods, we argue that directed
testing approaches and bug-pointing tools specialized for logic synthesis
applications can support the developers in detecting bugs earlier, can make
implementations more robust, and ultimately lead to a reduction in the time
and effort spend for debugging. Due to the large state space and homogeneity
of the commonly used netlist formats, general-purpose testing and debugging
tools often are incapable of providing the necessary performance to
efficiently test implementations of logic synthesis algorithms. The C++ logic
network library _mockturtle_ (Soeken et al., 2018; Riener et al., 2019b) has
deployed a framework for unit testing, continuous integration on various
operating systems and compilers, and a static code analysis engine controlled
by user-defined queries to aid developers.

In this paper, we present the latest additions to _mockturtle_ for testing and
debugging gate-level netlists: (1) a fuzz tester that repeatedly generates
small- and intermediate-sized netlists to hunt for bugs and (2) a testcase
minimizer to isolate the failure-inducing core of potentially lengthy bug
report. The two methods advance existing ones in the AIGER
utilities111https://github.com/arminbiere/aiger with the following key
highlights:

  1. (1)

Our methods are agnostic of the network type and support different gate-level
netlist formats. Although conceptually not hard to implement, to our knowledge
this is the first time that automated debugging techniques are available for
logic representations such as _Majority-Inverter Graphs_ (MIGs) or _Xor-And-
Graphs_ (XAGs). We demonstrate with a case study in Section 4.1 that testing
with more compact representations like XAGs increases the possibility of
capturing rare defects.

  2. (2)

Our implementations are tightly integrated into _mockturtle_ , which
eliminates interfacing overheads and provides about $10\times$ speed-up over
using external testing and debugging solutions.

  3. (3)

Our fuzz tester provides systematic approaches to test on small circuit
topologies in addition to purely-random networks. Experimental results show
that our topology-based fuzzer captures defects in ABC, mockturtle and
LSOracle using $93\%$ smaller testcases comparing to an existing AIG fuzzer
aigfuzz1.

  4. (4)

Our testcase minimizer guarantees to isolate a minimal failure-inducing core
and reduces testcases more efficiently by adopting specialized structural
reduction rules for gate-level netlists. Experimental results show that our
minimizer isolates smaller or equal-sized cores using $50\%$ oracle calls and
$50\%$ runtime comparing to an existing AIG delta debugger aigdd1.

##  2\. Background

###  2.1. Scope and Terminologies

_Logic networks_ are technology-independent representations of digital
circuits. They model combinational parts of gate-level circuits with directed
acyclic graphs, where vertices, or _nodes_ , represent logic gates and edges
represent interconnecting wires. Prominent examples of logic networks include
_And-Inverter Graph_ (AIG) (Kuehlmann et al., 2002), _Xor-And-Inverter Graph_
(XAG) (Hálecek et al., 2017), and _Majority-Inverter Graph_ (MIG) (Amaru et
al., 2015). Common terms related to structural properties of logic networks,
such as _primary input_ (PI), _primary output_ (PO), _transitive fanin cone_
(TFI), _transitive fanout cone_ (TFO), and _maximum fanout-free cone_ (MFFC),
are defined the same as in the literature. (Brayton and Mishchenko, 2006)

This paper focuses on testing and debugging software applications, referred to
as the _application under tests_ (AUTs), that take a logic network, called a
_testcase_ , as an input. Prominent examples of such applications include
implementations of logic synthesis algorithms such as rewriting (Mishchenko et
al., 2006a), resubstitution (Mishchenko et al., 2011) and technology mapping
(Calvino et al., 2022). Methods to verify the correctness of the results,
referred to as the _verification_ , are assumed to be provided. They may come
from several sources:

  * •

Assertions within the program.

  * •

Memory protection processes in the operating system checking for illegal
memory access (typically raising segmentation faults).

  * •

_Combinational equivalence checking_ (CEC) (Mishchenko et al., 2006b) of the
output network against the input testcase (for logic optimization algorithms).

  * •

Additional code checking coherence of the program’s internal data structures,
such as checking if the network is acyclic and checking the correctness of
reference counts, etc.

  * •

Another algorithm of the same purpose used to provide reference solutions (for
problems having an unique correct solution).

A failing verification, e.g., a non-equivalent CEC result, indicates that a
_defect_ of the AUT is observed and the testcase used is said to be _failure-
inducing_. The AUT combined with its verification is referred to as an
_oracle_ , and running the oracle with a testcase is an _oracle call_.

###  2.2. Fuzz Testing

_Fuzz testing_ (Miller et al., 1990) is a software testing technique heavily
used to detect security-related vulnerabilities and reliability issues. It is
conceptually simple, yet empirically powerful. A fuzzing algorithm involves
repeatedly generating testcases and using them to test the AUT. The idea of
fuzz testing first appeared in 1990, when spurious characters in the command
line caused by a noisy dial-up connection to a workstation led to,
surprisingly, crashes of the operating system. (Miller et al., 1990) Nowadays,
the generation of testcases in fuzz testing algorithms often involves
randomness, and the testcases are supposed to be beyond the expectation of the
AUT.

Various taxonomies of fuzz testing algorithms have been developed. For
example, black-box fuzzers (Lee et al., 2017) treat the AUT as a black-box
oracle and only observe its input/output behavior, whereas white-box fuzzers
(Godefroid et al., 2008; Cadar et al., 2008) analyze some internal information
of the AUT and generate testcases accordingly. Depending on the targeted types
of AUTs, some fuzzers generate testcases based on predefined models or
grammars (Dewey et al., 2014), whereas some other fuzzers mutate an initial
_seed_ testcase to generate more testcases (Cha et al., 2015). There are often
some parameters to be set for the testcase generators. A series of fuzz-tests
using testcases generated with a specific parameter configuration is called a
_fuzz testing campaign_. (Manès et al., 2021)

###  2.3. Delta Debugging and Testcase Minimization

Given two versions of the code of a program, where the first version works but
the second fails, _delta debugging_ (Zeller, 1999) is a method originally
proposed to extract a minimal set of changes (differences in the two versions
of code) that causes the failure. The algorithm was later extended for
minimizing failure-inducing testcases. (Zeller and Hildebrandt, 2002)

The basic idea of delta debugging is binary searching and dividing the set of
components, may it be the _delta_ between two versions of code or the input
testcase to a program, testing the program with the reduced set, keeping the
subsets that preserve the failure, and increasing the granularity of division.
The delta debugging algorithm (ddmin) guarantees to find a $1$-minimal subset
and requires, in the worst case, $n^{2}+3n$ oracle calls, where $n$ is the
size of the given set. (Zeller and Hildebrandt, 2002)

Besides delta debugging being a generic method for testcase minimization,
researchers have claimed that domain-specific testcase minimization techniques
are more effective and efficient for some applications such as tree-structured
inputs (Misherghi and Su, 2006), compilers (Regehr et al., 2012) and SMT
solvers (Kremer et al., 2021). Various open-source implementations of testcase
minimization tools exist, including the general-purposed
delta222https://github.com/dsw/delta, aigdd1 for the AIGER format,
ddSMT333http://fmv.jku.at/ddsmt/ for the SMT-LIB v2 format, and the LLVM
bugpoint tool444https://llvm.org/docs/Bugpoint.html. Inspired by delta
debugging, in this paper, we aim at providing such an effective testcase
minimization tool specialized for logic networks but not limited to AIGs.

##  3\. Testing and Debugging Toolkit

###  3.1. Testcase Generation

We develop a fuzz testing framework for testing any application that takes a
logic network as input. The AUT and the verification checks are provided as a
combined oracle call, thus categorizing it as a black-box fuzzer. Although in
some cases of fuzzing, testing with malformed testcases is key to test the
robustness of the AUT, this is not the case for our usage. In logic synthesis
applications, detecting and rejecting malformed inputs, e.g. a cyclic network,
are usually dealt by the parsers instead of the logic synthesis algorithms.
Nevertheless, as logic synthesis applications are often only tested with some
common benchmark suites, our fuzzing framework still tests them with a larger
input space beyond what they are usually tested with.

To generate random testcases, we propose three parameterized methods. These
methods apply to any type of network having a finite set of possible gate
types.

Random: Randomly generate nodes in topological order. This method is
parameterized by the starting number of PIs $n_{0}$, the starting number of
gates $m_{0}$, the number of networks $k$ of the same configuration to
generate, the increment of the number of PIs $\Delta n$ and of the number of
gates $\Delta m$. The generator starts from generating networks of $n=n_{0}$
PIs and $m=m_{0}$ gates and keeps a counter of how many networks have been
generated. After generating $k$ networks, the values of $n$ and $m$ are
increased by $\Delta n$ and $\Delta m$, respectively. Given the current values
of $n$ and $m$, a network is generated by:

  1. (1)

Create $n$ PIs.

  2. (2)

Randomly decide on a gate type. Assume that the type requires $\kappa$ fanins.

  3. (3)

Randomly sample $\kappa$ nodes (PIs or gates) that have been created.

  4. (4)

Randomly decide for each fanin if it is complemented.

  5. (5)

Create the gate. Repeat from step $2$ if the number of gates is smaller than
$m$.

  6. (6)

Assign all nodes without fanout to be POs.

For network types with trivial-case simplifications (e.g., in AIGs, attempting
to create an AND gate with identical fanins results in returning the fanin
without creating a gate) and structural hashing enabled, the number of gates
may not increase after step $4$. Thus, the loop of steps $2$ to $4$ may
iterate more than $m$ times and the terminating condition is when the actual
number of gates is $m$. If the parameters are set improperly, e.g., if $n=1$,
this might lead to an infinite loop.

Topology: Exhaustively enumerate all small-sized DAG topologies and randomly
concretize them. This method is parameterized by the starting number of gates
$m_{0}$, the lower $r_{l}$ and upper $r_{h}$ bounds on the PI-to-input ratio
and the number of networks $k$ of the same configuration to generate. Upon
initialization, the generator enumerates all isomorphic DAG topologies of
$m=m_{0}$ vertices using an algorithm implemented in (Haaswijk et al., 2020)
and randomly shuffles them. Then, it starts from generating networks of the
first topology and keeps a counter of how many networks have been generated.
After generating $k$ networks, the generator moves on to generating the next
topology. After all topologies have been used to generate $k$ networks, the
value of $m$ is incremented by $1$ and topologies of the increased size are
enumerated. Given a topology, which is specified by a DAG $G$ with hanging
inputs (i.e., the topology specifies how gates are connected to each other,
but not how they are connected to PIs), a random network is concretized by:

  1. (1)

Let $i$ be the number of hanging inputs in $G$. Randomly decide on an integer
$n$ such that $r_{l}\cdot i\leq n\leq r_{h}\cdot i$. Create $n$ PIs.

  2. (2)

For each input of $G$, randomly decide on a PI to connect to.

  3. (3)

For each vertex in $G$, randomly decide on a gate type.

  4. (4)

For each edge in $G$, randomly decide whether it is complemented.

  5. (5)

Assign the last gate to be a PO.

In step $1$, lower values of $n/i$ leads to higher probability that the
generated network reconverges on PIs, whereas higher values of $n/i$ leads to
higher probability to generate a tree-like network. The generated networks are
always single output.

Composed: Randomly compose a few small-sized DAG topologies to form a larger
network. This method is parameterized by the lower $m_{l}$ and upper $m_{h}$
bounds of the size of DAG topologies, the starting number of components
$c_{0}$, the starting number of PIs $n_{0}$, the number of networks $k$ of the
same configuration to generate, the increment of the number of PIs $\Delta n$
and of the number of components $\Delta c$. Upon initialization, the generator
enumerates all isomorphic DAG topologies of $m_{l}$ to $m_{h}$ vertices. Then,
it starts from generating networks of $n=n_{0}$ PIs and composed of $c=c_{0}$
components and keeps a counter of how many networks have been generated. After
generating $k$ networks, the values of $n$ and $c$ are increased by $\Delta n$
and $\Delta c$, respectively. Given the current values of $n$ and $c$, a
network is generated by:

  1. (1)

Create $n$ PIs.

  2. (2)

Randomly choose a topology $G$ from the list.

  3. (3)

For each hanging input of $G$, randomly decide on an existing node (a PI or a
node in a created component) to connect to.

  4. (4)

For each vertex in $G$, randomly decide on a gate type.

  5. (5)

For each edge in $G$, randomly decide whether it is complemented.

  6. (6)

If the number of created components is smaller than $c$, repeat from step $2$.

  7. (7)

Assign all nodes without fanout to be POs.

###  3.2. Testcase Minimization

(a) Remove PI: The TFO of $n$ is simplified.

(b) Remove PO: The MFFC of $n$ is removed.

(c) Substitute gate: The MFFC of $n$ is removed and the TFO of $n$ is
simplified.

(d) Simplify TFO: The TFO of $n$ is simplified.

(e) Remove MFFC: The MFFC of $n$ is removed.

(f) Remove gate: Only $n$ is removed.

Figure 1. Illustration of the reduction stages.

Assuming that the concerned defect is deterministic, there is a _core_ in any
given failure-inducing testcase, which is a subset of the testcase essential
for observing the defect. The other parts of the network are said to be
_irrelevant_ for observing the defect and can be removed. For example, for a
defect caused by the algorithm trying to insert an XOR gate into an AIG, which
is interpreted as inserting an AND gate instead, a core in the testcase may be
a subnetwork computing the XOR function. Due to the localized-computation
design style of modern scalable logic synthesis algorithms, the cores are
usually small-sized. We say that a core is _minimal_ if, for any node $n$,
removing $n$ results in never observing the defect again no matter how the
fanins and fanouts of $n$ are re-connected. A minimal core in a failure-
inducing testcase may or may not be unique. The goal of testcase minimization
is to find a minimal core in a given failure-inducing testcase.

We develop a testcase minimization tool for logic networks similar to delta
debugging but without adopting binary search. Given a network and an AUT with
verification (i.e. an oracle), our testcase minimizer iteratively tries to
reduce the network and tests if the defect is still observed. Only the
reduction operations that preserve observing the defect are kept; otherwise,
the operation is undone. Different reduction operations are tried in six
stages with increasing (finer) granularity as follows:

  1. (a)

_Remove PI_ : Substitute a PI $n$ with constant zero, thus simplifying its TFO
by constant propagation. In AIGs, some nodes in the TFO of $n$ that are
connected to $n$ without complement are removed, and so are their MFFCs.

  2. (b)

_Remove PO_ : Substitute a PO $n$ with constant zero, thus removing its MFFC.

  3. (c)

_Substitute gate_ : Substitute a gate $n$ with constant zero, thus removing
its MFFC and simplifying its TFO by constant propagation (as in (a)).

  4. (d)

_Simplify TFO_ : Assign fanins of a gate $n$ as new POs, and then substitute
$n$ with constant zero. This operation is less aggressive than the previous
one because only the TFO of $n$ is simplified and its MFFC is kept.

  5. (e)

_Remove MFFC_ : Substitute a gate $n$ with a new PI. This operation does not
cause constant propagation in its TFO and only removes the MFFC of $n$.

  6. (f)

_Remove gate_ : Assign fanins of a gate $n$ as new POs, and then substitute
$n$ with a new PI or with one of its fanins. Only $n$ is removed.

Figure 1 illustrates the effects of an operation in each of the reduction
stages. Regions filled in blue are removed after the operation, and regions
marked in yellow are simplified by constant propagation after the operation.
Wires and PIs or POs drawn in green are added after the operation.

The relative granularity of stages _remove PI_ and _remove PO_ depends on the
shape of the network. For networks with smaller TFO of PIs and less logic
sharing in the TFI of POs, _remove PO_ reduces the network faster; for
networks with smaller MFFC of POs and more reconvergences near the PIs,
_remove PI_ reduces the network faster. Thus, the first stage to apply is
heuristically decided by whether the network has more PIs than POs (_remove
PO_ is applied first) or more POs than PIs (_remove PI_ is applied first).

In each stage, the minimizer backs-up the current network, randomly samples a
PO or a gate as $n$ and performs the corresponding reduction operation. If the
defect is not observed anymore after reduction, the back-up is restored. This
procedure is repeated until all POs or all gates have been sampled, or until a
pre-defined number of operations have been tried.

The resulting network after minimization cannot be reduced anymore because the
last stage tries every possibility to remove one gate. Thus, by definition,
the minimized testcase is guaranteed to be a minimal core. However, minimal
cores are not necessarily unique, so it is possible that a different order of
reduction operations (e.g. by using a different random seed) results in a
smaller minimal core.

The minimized testcases are, in the most cases, highly destructed and cannot
be recognized or reverse-engineered anymore. Therefore, the testcase minimizer
does not only facilitate the debugging process, but also the communication
between developers when commercially-sensitive benchmarks are involved.

###  3.3. Usage Example

The testing and debugging toolkit described in this section is implemented in
mockturtle555Available: https://github.com/lsils/mockturtle as part of the
EPFL open-source logic synthesis libraries (Soeken et al., 2018). The toolkit
supports testing and debugging any application that takes a logic network,
written in AIGER (for AIGs) or Verilog (for other network types supported in
_mockturtle_ , such as XAGs and MIGs) formats, as input.

Figure 2 shows an example workflow of our toolkit. In this example, the
toolkit is used to fuzz test an algorithm implemented in _mockturtle_ (marked
in green), and then, if a defect is observed, minimizes the generated failure-
inducing testcase (marked in red). This can be done similarly for other
C++-based tools that include _mockturtle_ as a library.

⬇

1#include <mockturtle/mockturtle.hpp>

2using namespace mockturtle;

3

4int main()

5{

6 auto opt = [](aig_network aig) -> bool {

7 aig_network const aig_copy = aig.clone();

8 aig_resubstitution(aig);

9 aig_network const miter = *miter(aig_copy, aig);

10 return *equivalence_checking(miter);

11 };

12

13 fuzz_tester_params fuzz_ps;

14 fuzz_ps.file_format = fuzz_tester_params::aiger;

15 fuzz_ps.filename = "fuzz.aig";

16 fuzz_ps.timeout = 20; // 20 minutes

17 auto gen = random_aig_generator();

18 network_fuzz_tester<aig_network, decltype(gen)>

19 fuzzer(gen, fuzz_ps);

20 bool has_bug = fuzzer.run(opt);

21

22 if (!has_bug) return 0;

23

24 testcase_minimizer_params min_ps;

25 min_ps.file_format = testcase_minimizer_params::aiger;

26 min_ps.init_case = "fuzz";

27 min_ps.minimized_case = "fuzz_min";

28 testcase_minimizer<aig_network> minimizer(min_ps);

29 minimizer.run(opt);

30

31 aig_network aig;

32 lorina::read_aiger("fuzz_min.aig", aiger_reader(aig));

33 write_dot(aig, "fuzz_min.dot");

34 std::system("dot -Tpng -O fuzz_min.dot");

35

36 return 0;

37}

FuzzerMinimizerOracle

Figure 2. Example code to use the proposed toolkit to generate, minimize, and
visualize a failure-inducing testcase.

Our toolkit is also applicable for testing and debugging external tools. In
this case, the lambda function in lines $6$ to $11$ in Figure 2 shall be
replaced by one resembles the code in Figure 3.

⬇

6 auto opt = [](std::string filename) -> std::string {

7 return "abc -c \"read " + filename + "; rewrite\"";

8 };

Figure 3. Example code to use the toolkit for testing and debugging an
external tool, ABC.

Similar to aigfuzz and aigdd, calling the oracle as a system command requires
switching the program control through the command shell and interfacing the
testcases by reading and writing files. With the possibility of a tight
integration as in Figure 2, these interfacing overheads can be eliminated and,
empirically, making the automated testing and debugging workflow about
$10\times$ faster.

##  4\. Case Study

As a case study, we apply the toolkit on a known defect in a variation of _cut
rewriting_ , which uses a compatibility graph to identify compatible
substitution candidates (Riener et al., 2019a), implemented in
_mockturtle_.666The function cut_rewriting_with_compatibility_graph can be
found in algorithms/cut_rewriting.hpp. The defect can be observed by having a
cyclic network after applying the algorithm. The failure-inducing core of this
defect is shown in Figure 4(d). The cyclic result is caused by the algorithm
observing $n_{7}\oplus n_{2}$ as a substitution for $n_{11}$ and $n_{11}\oplus
n_{2}$ as a substitution for $n_{7}$, and trying to apply the two
substitutions at the same time. To identify that the two substitution
candidates are in conflict, the algorithm should check, for every pair $(A,B)$
of candidates, if the root of $A$ is contained in the cut of $B$ and the root
of $B$ is contained in the cut of $A$. This would be a feasible fix for the
defect, but would impact the efficiency of the algorithm. Another rewriting
algorithm that does not use the compatibility graph but eagerly substitutes
each candidate before searching for the next one is available in
_mockturtle_.777The function cut_rewriting can be found in the same header
file. However, when not affected by the defect, the defective algorithm has on
average better quality of result than eager rewriting. Also, the defect seems
to be observed very rarely, as will be discussed in Section 4.1. As a
compromise, both algorithms are kept in _mockturtle_.

The first reported failure-inducing testcase for this defect is shown in
Figure 4(a). The original testcase was not minimized by the reporter and have
$49$ PIs, $272$ AND gates, and $28$ POs. It took a human expert about $30$
minutes to manually reduce the testcase to Figure 4(d), with $3$ PIs, $8$
gates and $2$ POs. Using the testcase minimizer, the original testcase is
minimized to the same graph (subject to permutations of the two POs) within a
second and using $94$ oracle calls. In Section 4.2, we study the effectiveness
and necessity of the reduction stages described in Section 3.2.

(a) Before reduction, the original testcase is too big for human eyes to
understand.

(b) Remove PO only.

(c) Remove PO and substitute gate.

(d) The minimum failure-inducing testcase.

Figure 4. The failure-inducing testcase for an algorithm implemented in
_mockturtle_ and intermediate results of minimizing it.

###  4.1. Capturing The Defect with Fuzz Testing

####  4.1.1. Using AIGs

Knowing the existence of the defect, we investigate if our fuzz tester is
capable of generating another failure-inducing testcase. However, even though
the code line coverage has reached its maximum ($100\%$ excluding the lines
disabled by the algorithm’s options), the defect is not observed with more
than a billion ($10^{9}$) regular (i.e., without leveraging knowledge of the
known core) fuzz tests. Even if we limit the sampling space to the $3$-input,
$8$-gate, $2$-output topology as in Figure 4(d) and leaving only the
connections to PIs and edge complementations as random choices, there are
still $6^{2}\times 3^{4}\times 2^{16}=191\,102\,976$ different possible
networks, out of which only $3!\times 2^{3}=48$ networks (equivalent to Figure
4(d) subject to permutation and negation of PIs) are failure-inducing.

This case evidences that rare corner-case defects exist in logic synthesis
applications, and the identification of them may only rely on real-world
benchmarks. In these cases, the testcase minimization techniques are important
to automatize the extraction of the failure-inducing core, which facilitates
communication and debugging.

####  4.1.2. Using XAGs

We observe that the XOR functions in the core (nodes $9,10,11$ and nodes
$5,6,7$ in Figure 4(d)) are necessary. Using any of the randomized methods
described in Section 3.1, the possibility of generating an XOR function
composed of three AIG nodes is low. However, it is much more likely to
generate an XOR gate in an XAG. As the implementation is generic and works for
both AIGs and XAGs, we can try to capture the defect using XAGs instead. Table
1 shows that all the three methods successfully capture the defect within
reasonable runtime.

Table 1. Fuzzing the defective cut rewriting with XAGs. Method | #Tests | Time (s)
---|---|---
Random | 8150 | 1.8
Topology | 44498 | 6.6
Composed | 77573 | 22.8

###  4.2. Effects of The Reduction Stages

Given the initial failure-inducing testcase as in Figure 4(a), using the
default settings, our testcase minimizer produces the minimal failure-inducing
testcase as in Figure 4(d), which is a $97\%$ reduction rate in gate count.
The minimality can be proved by trying to remove each gate and seeing that any
possible resulting testcases are not failure-inducing.

Figures 4(b) and 4(c) show the reduction results if only some reduction stages
are applied. The first stage, remove PO (remove PI is skipped because there
are more PIs than POs), provides already $89\%$ reduction of the testcase by
removing large cones of irrelevant logic and quickly concentrates to the
transitive fanin cone of two POs (Figure 4(b), $30$ gates). The next stage,
substitute gate, further reduces the size to $15$ gates (Figure 4(c)), and the
failure-inducing core is easily observable (marked with a red box). However,
the other nodes on top of the core cannot be removed in this stage because
substituting any of them with constant zero also removes part of the core.
This can be accomplished by adding the stage simplify TFO, resulting in Figure
4(d). The two key operations are adding PO at nodes $13$ and $20$ and
substituting nodes $14$ and $21$ with constant zero. It is also possible to
reach the minimum by adding only the stage remove gate, but it requires at
least $6$ operations to remove nodes $14,15,16,21,22$ and $23$ one by one,
showing that this stage operates in a finer granularity. It may seem that the
stage remove MFFC is not necessary. However, this is only because the failure-
inducing core in this example does not have irrelevant transitive fanin gates
(i.e., it is connected to PIs) in the original testcase. When this is not the
case, the stages remove MFFC and/or remove gate are necessary to obtain the
minimum.

##  5\. Experimental Results

Table 2. Fuzz testing results. | aigfuzz | Random | Topology | Composed
---|---|---|---|---
| #Tests = $1000$ | #Tests = $1000$ | #Tests = $5000$ | #Tests = $5000$
AUT | #FITs | Size | Time | #FITs | Size | Time | #FITs | Size | Time | #FITs | Size | Time
mockturtle::aig_resubstitution | 0 | - | 10.3 | 0 | - | 3.5 | 0 | - | 0.02 | 1 | 14.0 | 0.03
mockturtle::sim_resubstitution | 3 | 812.3 | 22.3 | 0 | - | 4.2 | 6 | 5.0 | 0.06 | 93 | 21.7 | 0.11
abc> bms_start; if -u; strash | 952 | 2476.0 | 32.5 | 1000 | 950.0 | 14.6 | 1716 | 4.7 | 12.8 | 3749 | 20.3 | 13.0
abc> &if; &mfs -dael; &st | 956 | 2515.1 | 4.5 | 969 | 978.8 | 1.6 | 0 | - | 14.2 | 1047 | 23.9 | 12.3
abc> &mfsd; &st | 473 | 3935.9 | 30.5 | 584 | 1078.4 | 14.1 | 0 | - | 14.1 | 120 | 24.2 | 14.1
abc> &mfsd -cd; &st | 481 | 3959.7 | 130.0 | 73 | 1266.4 | 47.8 | 0 | - | 14.2 | 1 | 20.0 | 14.4
abc> if; mfse; strash | 458 | 2763.3 | 14.7 | 93 | 940.3 | 13.6 | 1 | 5.0 | 16.0 | 1056 | 23.4 | 15.0
abc> &stochsyn resub | 13 | 1164.8 | 14.6 | 0 | - | 6.0 | 0 | - | 12.5 | 14 | 18.9 | 12.5
lsoracle> aigscript | 1 | 7364.0 | 38.1 | 0 | - | 16.4 | 0 | - | 32.8 | 1 | 14.0 | 32.8
lsoracle> deep | 12 | 3227.3 | 41.6 | 0 | - | 21.5 | 0 | - | 33.3 | 6 | 23.0 | 32.8
lsoracle> xmgscript | 3 | 1056.0 | 21.6 | 2 | 350.0 | 10.5 | 38 | 4.9 | 11.5 | 99 | 20.1 | 12.0
Average |  | 2941.6 | 32.8 |  | 995.5 | 14.0 |  | 4.7 | 14.7 |  | 21.5 | 14.5

###  5.1. Fuzzing Open-Source Logic Synthesis Tools

To demonstrate the effectiveness of fuzzing and compare different testcase
generation methods, we fuzz-tested the following open-source logic synthesis
tools: _mockturtle_ 888Available: https://github.com/lsils/mockturtle. Commit
cf4769f. (Riener et al., 2019b), _ABC_ 999Available:
https://github.com/berkeley-abc/abc. Commit 31519bd. (Brayton and Mishchenko,
2010), and _LSOracle_ 101010Available: https://github.com/lnis-uofu/LSOracle.
Pull request #81. (Neto et al., 2019). Table 2 lists the commands or functions
where defects have been observed. Fuzz testing campaigns were conducted on
each AUT using aigfuzz and the three network generation methods described in
Section 3.1. In each campaign, aigfuzz and the method Random ran $1000$ tests,
whereas the methods Topology and Composed ran $5000$ tests. In Table 2, column
#FITs lists the total number of failure-inducing testcases generated, column
Size lists the average size (number of gates) of the failure-inducing
testscases, and column Time lists the total runtime in minutes including the
oracle calls.

The Composed method captured defects in all of the listed AUTs. On average,
Composed is about $2\times$ faster than aigfuzz and it tests on $5\times$ more
networks. This is because the Composed testcases are, on average, $7\%$ in
size comparing to those generated by aigfuzz. Also, notice that for AUTs in
_mockturtle_ , the runtimes of our fuzzing methods are about $10\times$ faster
than aigfuzz thanks to the tight integration.

Table 3. Testcase minimization results. |  | aigdd | Ours
---|---|---|---
AUT | Original size | Size | #Calls | Time | Size | #Calls | Time
mockturtle::cut_rewriting_with_compatibility_graph | 272 | 8 | 210 | 32.5 | 8 | 96 | 0.1
mockturtle::sim_resubstitution | 615 | 7 | 735 | 11.6 | 8 | 351 | 2.5
abc> &mfsd -cd; &st | 1050 | 31 | 1198 | 150.0 | 20 | 857 | 120.5
abc> if; mfse; strash | 1850 | 6 | 834 | 61.2 | 5 | 333 | 30.3
abc> &stochsyn resub | 3228 | 10 | 1124 | 59.6 | 8 | 411 | 21.1

###  5.2. Testcase Minimization

We compare our testcase minimizer to aigdd using the user-reported failure-
inducing testcase in Section 4 and four bigger testcases found by fuzz testing
in Section 5.1. In Table 3, column Size lists the number of gates of the
original and the minimized testcases, column #Calls lists the number of oracle
calls and column Time lists the total runtime in seconds. It can be observed
that our minimizer reduces the testcases into minimal cores of roughly the
same or smaller sizes comparing to aigdd, using on average $50\%$ oracle calls
and $50\%$ runtime.

##  6\. Conclusion and Discussion

In this paper, we survey automated testing and debugging techniques and
provide an open-sourced toolkit specialized for gate-level logic synthesis
applications. While random fuzz testing can already catch many higher-
frequency defects, the topology-based fuzzing methods provide a more
systematic approach to thoroughly test topology-related corner cases. After
failure-inducing testcases are found, the testcase minimizer can be used to
reduce their size efficiently to facilitate manual debugging (and also
anonymizing sensitive testcases). Moreover, our testcase minimization
technique guarantees to find a minimal core in the failure-inducing testcase,
which often gives insights on the cause of the defect and may also be used to
categorize testcases for the same AUT. The case study shows that (1) some
defects may be difficult to catch by fuzz testing, thus testcase minimization
is important when we need to rely on real-world testcases; and (2) testing
with more functionally-compact networks, such as XAGs, may help to detect some
defects in generic logic synthesis algorithms. In the remaining of this
section, we discuss more potentials of the toolkit and directions for future
research.

###  6.1. Non-deterministic Defects

Non-deterministic defects may be hard to debug because they cannot always be
reproduced. Non-determinism may come from a random number generator without a
fixed seed, a race condition in concurrent computation, or accessing to
uninitialized or unintended (index-out-of-bounds) memory. If a non-
deterministic defect is first observed with a large testcase, it may be
difficult to minimize it while maintaining the defect being observed. In such
cases, fuzz testing may help generating smaller testcases to observe the
defect deterministically.

###  6.2. Other Applications of The Toolkit

In addition to testing and debugging, the proposed tools can also be used for
finding examples with specific properties. For example, an open problem in
logic synthesis is whether it is better to heavily optimize an AIG before
transforming into MIG, or to perform optimization directly with an MIG. Our
toolkit can be used to generate minimal examples where one optimization script
obtains better results than the other, which might help researchers identify
weaknesses in the algorithms.

###  6.3. Future Works

Our network fuzzer currently does not support generating $k$-LUT networks
easily without specifying all possible LUT functions as different gate types.
This can be mitigated by integrating a random truth table generator.

In addition to minimizing the failure-inducing input networks, when the
defective AUT involves multiple independent algorithms (i.e., a _script_ with
a sequence of _commands_), it would also be helpful to minimize the script and
remove irrelevant commands. This can be accomplished by automatic binary
search, similar to delta debugging.

###### Acknowledgements.

We thank Max Austin for providing the original testcase discussed in Section
4.

## References

  * (1)
  * Amarú et al. (2015) Luca Amarú, Pierre-Emmanuel Gaillardon, and Giovanni De Micheli. 2015.  The EPFL combinational benchmark suite. In _IWLS 2015_.
  * Amaru et al. (2015) Luca Amaru, Pierre-Emmanuel Gaillardon, and Giovanni De Micheli. 2015.  Majority-inverter graph: A new paradigm for logic optimization.  _IEEE TCAD_ 35, 5 (2015), 806–819.
  * Brayton and Mishchenko (2006) Robert Brayton and Alan Mishchenko. 2006.  Scalable logic synthesis using a simple circuit structure. In _IWLS 2006_ , Vol. 6. 15–22.
  * Brayton and Mishchenko (2010) Robert K. Brayton and Alan Mishchenko. 2010.  ABC: An Academic Industrial-Strength Verification Tool. In _CAV 2010_. 24–40.
  * Cadar et al. (2008) Cristian Cadar, Daniel Dunbar, and Dawson R. Engler. 2008\.  KLEE: Unassisted and Automatic Generation of High-Coverage Tests for Complex Systems Programs. In _OSDI 2008_. USENIX Association, 209–224.
  * Calvino et al. (2022) Alessandro Tempia Calvino, Heinz Riener, Shubham Rai, Akash Kumar, and Giovanni De Micheli. 2022\.  A Versatile Mapping Approach for Technology Mapping and Graph Optimization. In _ASP-DAC 2022_. IEEE, 410–416.
  * Cha et al. (2015) Sang Kil Cha, Maverick Woo, and David Brumley. 2015\.  Program-Adaptive Mutational Fuzzing. In _SP 2015_. IEEE Computer Society, 725–741.
  * Dewey et al. (2014) Kyle Dewey, Jared Roesch, and Ben Hardekopf. 2014.  Language fuzzing using constraint logic programming. In _ASE 2014_. ACM, 725–730.
  * Godefroid et al. (2008) Patrice Godefroid, Michael Y. Levin, and David A. Molnar. 2008\.  Automated Whitebox Fuzz Testing. In _NDSS 2008_. The Internet Society.
  * Haaswijk et al. (2020) Winston Haaswijk, Mathias Soeken, Alan Mishchenko, and Giovanni De Micheli. 2020.  SAT-Based Exact Synthesis: Encodings, Topology Families, and Parallelism.  _IEEE TCAD_ 39, 4 (2020), 871–884.
  * Hálecek et al. (2017) Ivo Hálecek, Petr Fiser, and Jan Schmidt. 2017\.  Are XORs in logic synthesis really necessary?. In _DDECS 2017_. 134–139.
  * Kremer et al. (2021) Gereon Kremer, Aina Niemetz, and Mathias Preiner. 2021\.  ddSMT 2.0: Better Delta Debugging for the SMT-LIBv2 Language and Friends. In _CAV 2021_. Springer, 231–242.
  * Kuehlmann et al. (2002) Andreas Kuehlmann, Viresh Paruthi, Florian Krohm, and Malay K. Ganai. 2002.  Robust Boolean reasoning for equivalence checking and functional property verification.  _IEEE TCAD_ 21, 12 (2002), 1377–1394.
  * Lee et al. (2017) Seungsoo Lee, Changhoon Yoon, Chanhee Lee, Seungwon Shin, Vinod Yegneswaran, and Phillip A. Porras. 2017.  DELTA: A Security Assessment Framework for Software-Defined Networks. In _NDSS 2017_. The Internet Society.
  * Manès et al. (2021) Valentin J. M. Manès, HyungSeok Han, Choongwoo Han, Sang Kil Cha, Manuel Egele, Edward J. Schwartz, and Maverick Woo. 2021\.  The Art, Science, and Engineering of Fuzzing: A Survey.  _IEEE Trans. Software Eng._ 47, 11 (2021), 2312–2331.
  * Miller et al. (1990) Barton P. Miller, Lars Fredriksen, and Bryan So. 1990\.  An Empirical Study of the Reliability of UNIX Utilities.  _Commun. ACM_ 33, 12 (1990), 32–44.
  * Mishchenko et al. (2011) Alan Mishchenko, Robert K. Brayton, Jie-Hong R. Jiang, and Stephen Jang. 2011.  Scalable don’t-care-based logic optimization and resynthesis.  _ACM Trans. Reconfigurable Technol. Syst._ 4, 4 (2011), 34:1–34:23.
  * Mishchenko et al. (2006a) Alan Mishchenko, Satrajit Chatterjee, and Robert K. Brayton. 2006a.  DAG-aware AIG rewriting: A fresh look at combinational logic synthesis. In _DAC 2006_. 532–535.
  * Mishchenko et al. (2006b) Alan Mishchenko, Satrajit Chatterjee, Robert K. Brayton, and Niklas Eén. 2006b.  Improvements to combinational equivalence checking. In _ICCAD 2006_. ACM, 836–843.
  * Misherghi and Su (2006) Ghassan Misherghi and Zhendong Su. 2006.  HDD: Hierarchical Delta Debugging. In _ICSE 2006_. ACM, 142–151.
  * Neto et al. (2019) Walter Lau Neto, Max Austin, Scott Temple, Luca G. Amarù, Xifan Tang, and Pierre-Emmanuel Gaillardon. 2019\.  LSOracle: a Logic Synthesis Framework Driven by Artificial Intelligence: Invited Paper. In _ICCAD 2019_. ACM, 1–6.
  * Regehr et al. (2012) John Regehr, Yang Chen, Pascal Cuoq, Eric Eide, Chucky Ellison, and Xuejun Yang. 2012\.  Test-case reduction for C compiler bugs. In _PLDI 2012_. ACM, 335–346.
  * Riener et al. (2019a) Heinz Riener, Winston Haaswijk, Alan Mishchenko, Giovanni De Micheli, and Mathias Soeken. 2019a.  On-the-fly and DAG-aware: Rewriting Boolean Networks with Exact Synthesis. In _DATE 2019_. IEEE, 1649–1654.
  * Riener et al. (2019b) Heinz Riener, Eleonora Testa, Winston Haaswijk, Alan Mishchenko, Luca G. Amarù, Giovanni De Micheli, and Mathias Soeken. 2019b.  Scalable Generic Logic Synthesis: One Approach to Rule Them All. In _DAC 2019_. ACM, 70.
  * Soeken et al. (2018) Mathias Soeken, Heinz Riener, Winston Haaswijk, Eleonora Testa, Bruno Schmitt, Giulia Meuli, Fereshte Mozafari, and Giovanni De Micheli. 2018.  The EPFL logic synthesis libraries.  _arXiv preprint arXiv:1805.05121_ (2018).
  * Zeller (1999) Andreas Zeller. 1999\.  Yesterday, My Program Worked. Today, It Does Not. Why?. In _SIGSOFT 1999_. Springer, 253–267.
  * Zeller and Hildebrandt (2002) Andreas Zeller and Ralf Hildebrandt. 2002.  Simplifying and Isolating Failure-Inducing Input.  _IEEE Trans. Software Eng._ 28, 2 (2002), 183–200.


# Applying Large Language Models API to Issue Classification Problem

Gabriel Aracena<EMAIL_ADDRESS>Grand Canyon University3300 W Camelback
RdPhoenixArizonaUSA85017 ,  Kyle Luster<EMAIL_ADDRESS>Grand Canyon
University3300 W Camelback RdPhoenixArizonaUSA85017 ,  Fabio Santos
<EMAIL_ADDRESS>Grand Canyon University3300 W Camelback
RdPhoenixArizonaUSA ,  Igor Steinmacher<EMAIL_ADDRESS>Northern
Arizona UniversityFlagstaffArizonaUSA and  Marco A. Gerosa
<EMAIL_ADDRESS>Northern Arizona University1900 S Knoles
Dr.FlagstaffArizonaUSA

###### Abstract.

Effective prioritization of issue reports is crucial in software engineering
to optimize resource allocation and address critical problems promptly.
However, the manual classification of issue reports for prioritization is
laborious and lacks scalability. Alternatively, many open source software
(OSS) projects employ automated processes for this task, albeit relying on
substantial datasets for adequate training. This research seeks to devise an
automated approach that ensures reliability in issue prioritization, even when
trained on smaller datasets. Our proposed methodology harnesses the power of
Generative Pre-trained Transformers (GPT), recognizing their potential to
efficiently handle this task. By leveraging the capabilities of such models,
we aim to develop a robust system for prioritizing issue reports accurately,
mitigating the necessity for extensive training data while maintaining
reliability. In our research, we have developed a reliable GPT-based approach
to accurately label and prioritize issue reports with a reduced training
dataset. By reducing reliance on massive data requirements and focusing on
few-shot fine-tuning, our methodology offers a more accessible and efficient
solution for issue prioritization in software engineering. Our model predicted
issue types in individual projects up to 93.2% in precision, 95% in recall,
and 89.3% in F1-score.

Issue Report Classification, Large Language Model, Natural Language
Processing, Software Engineering, Labeling, Multi-class Classification,
Empirical Study

††conference: 46th International Conference on Software Engineering; April
2024; Lisbon, Portugal

##  1\. Introduction

The onboarding of newcomers is important to keep OSS projects sustainable
(Steinmacher et al., 2015b). One of the initial steps of the onboarding
process in an OSS project is to find an appropriate task (e.g. bugs, features,
etc) to work with. The literature shows that this is a crucial step to
determine the future of the newcomer in the project (Wang and Sarma, 2011;
Steinmacher et al., 2015a). One strategy adopted by the communities is to add
labels to the issues to help new contributors find the most appropriate ones
(Steinmacher et al., 2018; Santos et al., 2022). However, labeling issues in
big projects is time-consuming and demands efforts from the (already
overloaded) maintainers (Barcomb et al., 2020).

More recently, many researchers proposed approaches to label issue types
automatically to help managers prioritize and allocate better available
resources. Kallis et al. (2019, 2021) use fastText to classify issues as bug,
feature or question. Still, Colavito et al. (2023) employed SETFIT in the last
NLBSE competition to predict issue types. Santos et al. (2021) predicted
skills to solve an issue using API domains as a proxy. The work was extended
to use Social Network Analysis (SNA), improving the predictions (Santos et
al., 2023). Finally, a tool is available to OSS communities to recommend
issues based on skills informed by developers (Vargovich et al., 2023).

In this study, we leverage OpenAI API to create a fine-tuned model to classify
issues as bugs, features, or questions. We reached an F1-score of 82.8%.
OpenAI is the innovative company behind the development of ChatGPT—the most
notorious of the many Large Language Models (LLM) they have built. An LLM is a
sophisticated neural network model that undergoes training using extensive
datasets, including books, code, articles, and websites. This training enables
the model to grasp the inherent patterns and relationships within the language
for which it was trained. Consequently, the LLM can produce cohesive content,
such as grammatically accurate sentences and paragraphs, replicating human
language, or syntactically precise code snippets (Ozkaya, 2023) and it is
capable of adapting incredibly when fine-tuned.

RQ1: To what extent can we predict the issue types using OpenAI’s fine-tuning
API? To answer RQ1, we fine-tuned the gpt-3.5-turbo base model provided in the
OpenAI API. Fine-tuning is the process of giving specific and niched training
for a pre-trained model. Fine-tuning through the OpenAI API is a multi-step
process that involves simulating conversations with the LLM and telling them
the expected response. We used the title and body of the issues in our
training data as part of our prompt and the correct label as the expected
response.

Overall, we found that by pre-processing the issue title and body, we can
predict the issue types with a macro average of 83.24% precision, 82.87%
recall, and 82.8% F-measure. This yield barely surpassed the baseline reported
in the competition (Kallis et al., 2024).

##  2\. Method

Figure 1 depicts our method, composed of the data preprocessing, model
implementation and training, model evaluation, and analysis phases.

Figure 1. Method

###  2.1. Data Preprocessing and Cleaning

####  2.1.1. Introduction to the Dataset

The dataset for the NLBSE’24 Tool Competition on Issue Report Classification
is a collection of 3,000 labeled issue reports, which have been extracted from
five open-source projects. The data was collected over 21 months, from January
2022 to September 2023, ensuring a wide range of issues and scenarios are
covered.

####  2.1.2. Attributes of Each Issue Report

Each issue report in the dataset is characterized by four key attributes:

  1. (1)

Repository: The name of the open-source project from which the issue report
was extracted.

  2. (2)

Label: The category that the issue report falls into.

  3. (3)

Title: The title of the issue report.

  4. (4)

Body: The main content of the issue report.

####  2.1.3. Labeling and Exclusions

Each issue has only one label; labeled either bug, feature, or question.

####  2.1.4. Noise Removal and Data Preparation

  * •

Method 1: The method involves the removal of double quotation marks,
elimination of specific string patterns, lowercase conversion for
standardization, and removal of emojis, URLs, HTML tags, special characters,
and punctuation. The method also addressed consecutive whitespace and
restricted word length to 20 characters, as any string longer than that is not
likely to be a word but noise.

  * •

Method 2: The second method mirrors Method 1’s cleaning process with a handful
of appropriate modifications. It eliminates more string patterns, modifies
handling URLs and HTML tags by substituting them with universal identifiers
(¡URL¿ and ¡HTML_TAG¿), and replaces usernames and image links with their own
identifiers, ¡USER¿ and ¡IMAGE¿, respectively. Lastly, it strips Markdown
syntax from the text, striving to preserve only the tokens necessary for
analysis.

####  2.1.5. Data Segmentation and Labeling

The CSV file was split into five repositories, each with 300 categorized issue
reports (”bug,” ”feature,” or ”question”), and the data provided was
prelabeled.

####  2.1.6. Format Conversion for Model Input

Repository training data frames were converted into JSON line files,
structured as a conversation, and handed off the to API. Each file contains a
prompt, (user_message). We decided to use the prompt, ”Classify, IN ONLY 1
WORD, the following GitHub issue as ’feature’, ’bug’, or ’question’ based on
its title and body:”. The second half of the conversation is called
(assistant_message), and it contains the model’s classification (’bug,’
’feature,’ or ’question’). Both halves are concatenated and assigned to the
variable (conversation_message), these variables are then appended iteratively
into a single JSON line file.

###  2.2. Model Implementation and Training

####  2.2.1. Invoking the API

The API invoked in our code is OpenAI’s fine-tuning API. Our chosen model is
the gpt-3.5-turbo model for natural language understanding and generation
tasks. This API enables interaction with language models capable of
understanding prompts and generating coherent and contextually relevant
responses. We invoked the API using OpenAI’s Python library.

Firstly, we invoke the OpenAI API. Next, the training files are uploaded to
the server. Using these files, gpt-3.5-turbo creates fine-tuned models for
each repo. These models will be retrieved for future use. To test the model,
the interaction with the API occurs through the
create()111openai.chat.completions.create() method, where a user prompt is
constructed. Here we reuse the prompt from the training cycle, append the
testing data, and pass it to the API. The constructed prompt returns its
classification of the issue. The API invocation involves parameters such as
the model to use, the maximum number of tokens to generate, and the
temperature for controlling the randomness of responses—all of which have been
tuned to yield optimal results. The model utilized was the fine-tuned model
corresponding to its testing dataset and the maximum number of tokens to be
returned was set to 1. The strings ’feature,’ ’bug,’ and ’label,’ were all
verified by the OpenAI Tokenizer (https://platform.openai.com/tokenizer) to
have 1 token each. The temperature was set to 0.0 to minimize randomness in
the answers, providing consistent results.

####  2.2.2. Model Fine-tuning Process

Fine-tuning a model through OpenAI’s API involves a systematic multi-step
procedure that requires a comprehensive grasp of the API documentation. As
previously outlined, the fine-tuning process was tailored for each repository,
demanding dedicated models for enhanced performance.

As explained in the ”Format Conversion for Model Input” section, we created
JSON line files customized for individual repositories. These files were
uploaded to OpenAI’s server to serve as training data for fine-tuning the
models. To start the fine-tuning process, we initiated a job to refine the
base model using the specified training file. Each job was queued in the cloud
environment, leading us to regularly check their statuses every 30 minutes.
After around 5 hours, all jobs were finished, and the fine-tuned models were
prepared for use.

Upon completion, the server assigned unique identifiers for each fine-tuned
model. For instance, the model tailored for the ’facebook/react’ repository
was assigned the ID ft:gpt-3.5-turbo-0613:gcucst440:fb-
issueclassifier:8LLGMnAI.

Initially, the default hyperparameters were used during the fine-tuning
process, automatically configuring the learning rate multiplier, number of
epochs, and batch size. All models began with the default number of 3 epochs;
however, as we conducted our training, step metrics revealed room for
improvement in certain models. Given this, each model’s epoch count was
tailored for optimal performance. Future improvements might involve fine-
tuning other hyperparameters for optimization.

###  2.3. Performance Evaluation Metrics

We obtained our results by comparing the predictions with the ground truth. To
do this, two lists were created, one with the correct labels from the testing
dataset and one with the predicted labels from the fine-tuned model. We used
precision_score, recall_score, and f1_score from sklearn.metrics to
standardize the results obtained across all repositories. Using the metrics
functions from sklearn and the lists, we were capable of calculating
precision, recall, and f1-score for all models.

###  2.4. Getting the results

After computing metrics for all repositories, we calculated the average for
each metric and each label to obtain the overall results present in table 1.

##  3\. Results

To answer our RQ1, (to what extent can we predict the issue types using
OpenAI’s fine-tuning API?) we tested different repo datasets to their
respective fine-tuned model.

Table 1 shows the average f1-score results varied from 76.65% to 87.08%. This
can be explained by the differences in how issues were written and the
particularities of each repository. Overall, when using title and body
combined we reached overall precision of 83.24% recall of 82.87% and F1-score
of 82.80%

Table 1. Detailed Issue Report Classification Complete Table: Metrics by Repo
and by label

CM = Cleaning Method ; E = Total Epochs ; P = Precision ; R = Recall  Repo CM
E Label P R F1 facebook 1 3 bug 0.8333 0.9500 0.8878 facebook 1 3 feature
0.8557 0.8900 0.8725 facebook 1 3 question 0.9024 0.7400 0.8132 facebook 1 3
average 0.8635 0.8600 0.8579 tensorflow 2 10 bug 0.9072 0.8800 0.8934
tensorflow 2 10 feature 0.9318 0.8200 0.8723 tensorflow 2 10 question 0.7913
0.9100 0.8465 tensorflow 2 10 average 0.8768 0.8700 0.8708 microsoft 1 6 bug
0.8511 0.8000 0.8247 microsoft 1 6 feature 0.8131 0.8700 0.8406 microsoft 1 6
question 0.7980 0.7900 0.7938 microsoft 1 6 average 0.8207 0.8200 0.8198
bitcoin 1 3 bug 0.7339 0.8000 0.7656 bitcoin 1 3 feature 0.8318 0.8900 0.8599
bitcoin 1 3 question 0.7381 0.6200 0.6739 bitcoin 1 3 average 0.7679 0.7700
0.7665 opencv 2 6 bug 0.7288 0.8600 0.7890 opencv 2 6 feature 0.9091 0.8000
0.8511 opencv 2 6 question 0.8617 0.8100 0.8351 opencv 2 6 average 0.8332
0.8233 0.8250 overall NA NA bug 0.8109 0.8580 0.8321 overall NA NA feature
0.8683 0.8540 0.8593 overall NA NA question 0.8183 0.7740 0.7925 overall NA NA
average 0.8324 0.8287 0.8280

_RQ1 Summary._ It is possible to predict the GitHub Issue labels with
precision of 83.24%, recall of 82.87%, and F-measure of 82.8% using fine-tuned
gpt-3.5-turbo base models, with title and body as features. 222 Check the full
repository at https://github.com/G4BE-334/NLBSE-issue-report-classification

##  4\. Discussion

Observing the complete results (Table 1) something fascinating caught our
eyes: why are the metrics so different regarding both the repository and the
label? The issues labeled as questions were by far the worst on (almost) every
repository. Why is that? It seems that question is a bad label name for GitHub
issues. It seems to be related to the fact that question is just a very broad
label that consequently causes users to label issues as a question wrongfully,
and they could be better labeled as something else. When analyzing the data
and checking the question label issues, it is very hard even to define a
question label issue when reading the title and body. When compared to feature
and bug, it is clear that question issues are not very well defined.

Similarly, when comparing the metrics on different repositories it is clear
that the results achieved for the bitcoin repository were worse when compared
to the other repos. When we compare the F1-score with the tensorflow repo
(87.08%) the F1-score of the bitcoin repo is more than 10% worse (76.65%). Why
are the results so different across different repositories? After further
analysis, we concluded that it is due to bad labeling and description of the
issues by the developers who work on each repository. We were able to conclude
that by comparing our results with the baseline metrics and saw that the
baseline model had the same issue, so it is clear to us that the model
performed poorly because of the data. Additionally, we saw that many of the
Bitcoin issues were written without much clarity, solidifying our hypothesis.

What are the difficulties in labeling? Each repository has specific concepts,
technologies, and domain-related topics that vary from one repo to another.
Moreover, the issue description style is also different, making automated
labeling approaches more challenging.

Looking at the confusion matrix below in Table 2, we can see models have
varying degrees of success in classifying different types of issues (bugs,
features, questions) across the different repositories. The model performs
consistently in identifying ’bug’ labels across repositories, with TP ranging
from 80 to 89, suggesting that the features used by the model are good
indicators of this class. The models seem to perform well on ’feature’
classification, with relatively high TP and higher FP than ’bug’
classification. This could indicate confusion between ’feature’ and other
types of issues, leading to more false alarms. There is a notable variance in
the model’s ability to correctly classify ’question’ labels, with the lowest
TP observed in the ’bitcoin/bitcoin’ repository.

The ’facebook/react’ repository has relatively balanced classification across
all labels, indicating that the model may have learned distinctive features of
each label well in this context. The ’tensorflow/tensorflow’ repository has
the highest FP for ’question’ classification, suggesting the potential over-
classification of this label. The ’microsoft/vscode’ repository tends to miss
’feature’ and ’question’ issues (as indicated by higher FN).

Table 2. Confusion Matrix for all projects and labels Repository | Label | TP | FP | FN | TN
---|---|---|---|---|---
facebook/react | bug | 89 | 15 | 11 | 185
facebook/react | feature | 95 | 19 | 5 | 181
facebook/react | question | 74 | 8 | 26 | 192
tensorflow/tensorflow | bug | 82 | 6 | 18 | 194
tensorflow/tensorflow | feature | 88 | 9 | 12 | 191
tensorflow/tensorflow | question | 91 | 24 | 9 | 176
microsoft/vscode | bug | 87 | 20 | 13 | 180
microsoft/vscode | feature | 80 | 14 | 20 | 186
microsoft/vscode | question | 79 | 20 | 21 | 180
bitcoin/bitcoin | bug | 89 | 18 | 11 | 182
bitcoin/bitcoin | feature | 80 | 29 | 20 | 171
bitcoin/bitcoin | question | 62 | 22 | 38 | 178
opencv/opencv | bug | 80 | 8 | 20 | 192
opencv/opencv | feature | 86 | 32 | 14 | 168
opencv/opencv | question | 81 | 13 | 19 | 187

Our models could likely benefit from additional tuning or training data to
improve classification, especially for ’question’ labels. Addressing the
imbalance between FP and FN across different labels could help improve model
performance. This might involve re-evaluating the features used for
classification or introducing class weights during training.

When compared to the baseline model results provided by the NLBSE Tool
Competition Department our model performed slightly better overall and on some
specific repos. The baseline model utilized the all-mpnet-base-v2 sentence
transformer developed by hugging faces as their base model and fine-tuned it
with SetFitTrainer. The baseline model had an overall average f1-score of
82.7% when we got 82.8%. The average f1-score on the tensorflow, bitcoin, and
opencv repos for the baseline model was 86.44%, 75.55%, and 81.73%
respectively. Meanwhile, our models got 87.08%, 76.65%, and 82.5% average
f1-score on the same repos respectively.

##  5\. Conclusion

In conclusion, this study represents a significant step in applying large
language models, specifically OpenAI’s gpt-3.5-turbo, to classify GitHub issue
reports. By fine-tuning models on datasets from five distinct repositories, we
demonstrated the feasibility and efficiency of this approach. Our methodology,
focusing on data preprocessing and model fine-tuning, yielded an average
F1-score of 82.8%, barely surpassing the baseline model’s effectiveness in
classifying issues into ’bug,’ ’feature,’ or ’question’ categories. This
performance, however, varied across repositories, revealing the nuanced nature
of issue report classification.

One of the key findings was the variability in performance based on the nature
of the data in each repository. This underscores the need for tailored
approaches when applying language models in different contexts. Furthermore,
the study highlighted challenges in classifying ’question’ labels due to their
often ambiguous nature. This points to a broader issue in the standardization
of labeling practices within the GitHub community.

## Acknowledgments

This work is supported in part by the NAU computer science research team, as
well as Dr. Isac Artzi of GCU.

## References

  * (1)
  * Barcomb et al. (2020) A. Barcomb, K. Stol, B. Fitzgerald, and D. Riehle. 2020.  Managing Episodic Volunteers in Free/Libre/Open Source Software Communities.  _IEEE Transactions on Software Engineering_ (2020), 1–1.
  * Colavito et al. (2023) Giuseppe Colavito, Filippo Lanubile, and Nicole Novielli. 2023.  Few-Shot Learning for Issue Report Classification. In _2023 IEEE/ACM 2nd International Workshop on Natural Language-Based Software Engineering (NLBSE)_. 16–19.  https://doi.org/10.1109/NLBSE59153.2023.00011
  * Kallis et al. (2024) Rafael Kallis, Giuseppe Colavito, Ali Al-Kaswan, Luca Pascarella, Oscar Chaparro, and Pooja Rani. 2024.  The NLBSE’24 Tool Competition. In _Proceedings of The 3rd International Workshop on Natural Language-based Software Engineering (NLBSE’24)_.
  * Kallis et al. (2019) Rafael Kallis, Andrea Di Sorbo, Gerardo Canfora, and Sebastiano Panichella. 2019.  Ticket Tagger: Machine Learning Driven Issue Classification. In _2019 IEEE International Conference on Software Maintenance and Evolution, ICSME 2019, Cleveland, OH, USA, September 29 - October 4, 2019_. IEEE, 406–409.  https://doi.org/10.1109/ICSME.2019.00070
  * Kallis et al. (2021) Rafael Kallis, Andrea Di Sorbo, Gerardo Canfora, and Sebastiano Panichella. 2021.  Predicting issue types on GitHub.  _Science of Computer Programming_ 205 (2021), 102598.  https://doi.org/10.1016/j.scico.2020.102598
  * Ozkaya (2023) Ipek Ozkaya. 2023.  Application of Large Language Models to Software Engineering Tasks: Opportunities, Risks, and Implications.  _IEEE Software_ 40, 3 (2023), 4–8.
  * Santos et al. (2023) Fabio Santos, Jacob Penney, João Felipe Pimentel, Igor Wiese, Bianca Trinkenreich, Igor Steinmacher, and Marco A Gerosa. 2023.  Tell Me Who Are You Talking to and I Will Tell You What Issues Need Your Skills. In _2023 IEEE/ACM 20th International Conference on Mining Software Repositories (MSR)_.
  * Santos et al. (2022) Fabio Santos, Bianca Trinkenreich, João Felipe Nicolati Pimentel, Igor Wiese, Igor Steinmacher, Anita Sarma, and Marco Gerosa. 2022.  How to choose a task? Mismatches in perspectives of newcomers and existing contributors.  _Empirical Software Engineering and Measurement_ (2022).
  * Santos et al. (2021) Fabio Santos, Igor Wiese, Bianca Trinkenreich, Igor Steinmacher, Anita Sarma, and Marco Gerosa. 2021.  Can I Solve It? Identifying APIs Required to Complete OSS Task.  (2021).
  * Steinmacher et al. (2015a) Igor Steinmacher, Tayana Uchôa Conte, and Marco Aurélio Gerosa. 2015a.  Understanding and supporting the choice of an appropriate task to start with in open source software communities. In _2015 48th Hawaii International Conference on System Sciences_. IEEE, 5299–5308.
  * Steinmacher et al. (2015b) Igor Steinmacher, Marco Aurelio Graciotto Silva, Marco Aurelio Gerosa, and David F Redmiles. 2015b.  A systematic literature review on the barriers faced by newcomers to open source software projects.  _Information and Software Technology_ 59 (2015), 67–85.
  * Steinmacher et al. (2018) Igor Steinmacher, Christoph Treude, and Marco Aurelio Gerosa. 2018.  Let me in: Guidelines for the successful onboarding of newcomers to open source projects.  _IEEE Software_ 36, 4 (2018), 41–49.
  * Vargovich et al. (2023) Joseph Vargovich, Fabio Santos, Jacob Penney, Marco Aurélio Gerosa, and Igor Steinmacher. 2023.  GiveMeLabeledIssues: An Open Source Issue Recommendation System. In _20th IEEE/ACM International Conference on Mining Software Repositories, MSR 2023, Melbourne, Australia, May 15-16, 2023_. IEEE, 402–406.  https://doi.org/10.1109/MSR59073.2023.00061
  * Wang and Sarma (2011) Jianguo Wang and Anita Sarma. 2011.  Which bug should I fix: helping new developers onboard a new project. In _Proceedings of the 4th International Workshop on Cooperative and Human Aspects of Software Engineering_. ACM, 76–79.