#  : GNN-Guided Automatic Code Parallelization using Large Language Models

Quazi Ishtiaque Mahmud *  Department of Computer Science, Iowa State
University, Ames, Iowa, USA
{mahmud, tehrani, hungphd<EMAIL_ADDRESS>Ali TehraniJamsaz
Department of Computer Science, Iowa State University, Ames, Iowa, USA
{mahmud, tehrani, hungphd<EMAIL_ADDRESS>Hung D Phan  Department of
Computer Science, Iowa State University, Ames, Iowa, USA
{mahmud, tehrani, hungphd<EMAIL_ADDRESS>Nesreen K. Ahmed  Intel
Labs, Santa Clara, CA, USA
<EMAIL_ADDRESS>
Ali Jannesari  Department of Computer Science, Iowa State University, Ames,
Iowa, USA
{mahmud, tehrani, hungphd<EMAIL_ADDRESS>
###### Abstract

Parallelizing sequentially written programs is a challenging task. Even
experienced developers need to spend considerable time finding parallelism
opportunities and then actually writing parallel versions of sequentially
written programs. To address this issue, we present , a framework for
automatically discovering parallelism and generating the parallel version of
the sequentially written program. Our framework consists of two major
components: i) a heterogeneous Graph Neural Network (GNN) based parallelism
discovery and parallel pattern detection module, and ii) an LLM-based code
generator to generate the parallel counterpart of the sequential programs. We
use the GNN to learn the flow-aware characteristics of the programs to
identify parallel regions in sequential programs and then construct an
enhanced prompt using the GNN’s results for the LLM-based generator to finally
produce the parallel counterparts of the sequential programs. We evaluate on
11 applications of 2 well-known benchmark suites: NAS Parallel Benchmark and
Rodinia Benchmark. Our results show that is indeed effective in improving the
state-of-the-art LLM-based models for the task of parallel code generation in
terms of multiple code generation metrics. also improves the average runtime
of the parallel code generated by the state-of-the-art LLMs by as high as 3.4%
and 2.9% for the NAS Parallel Benchmark and Rodinia Benchmark respectively.
Additionally, to overcome the issue that well-known metrics for translation
evaluation have not been optimized to evaluate the quality of the generated
parallel code, we propose OMPScore for evaluating the quality of the generated
code. We show that OMPScore exhibits a better correlation with human judgment
than existing metrics, measured by up to 75% improvement of Spearman
correlation.

##  1 Introduction

††footnotetext: * These authors have contributed equally to this work.

The rise in the number of on-chip cores has led to more frequent development
of parallel code. Nevertheless, to unleash the capabilities of multi-core
systems, the need for developing parallel programs will continue to grow.
However, developing parallel programs is not a trivial task. The communication
among cores, effective data sharing among the threads, synchronization, and
many other factors need to be considered while crafting parallel programs,
which makes the process of developing parallel programs far more complex than
serial ones.

HPC communities have published different tools and programming models to ease
the process of moving from serial to parallel code. One of the well-
established parallel programming models is OpenMP, which is a directive-based
programming model that allows users to parallelize sequential code with
minimal changes. Most modern compilers recognize and support parallelization
through OpenMP constructs. However, even with OpenMP, developers must
carefully decide which clauses or directives they need to use. Inappropriate
usage of clauses can cause concurrency bugs such as data race or decrease
performance. Therefore, tools such as DiscoPoP (Li et al., 2015) were
developed that can automatically discover parallelism opportunities and insert
OpenMP constructs. However, due to the conservativeness of these tools, they
sometimes miss potential parallelization opportunities.

Nowadays, with the advancements in deep learning, various deep learning
approaches have been proposed to identify parallelism and advise OpenMP
constructs (Chen et al., 2023a; Harel et al., 2023; Shen et al., 2023; Kadosh
et al., 2023). In this paper, we propose . An approach that leverages Large
Language Models (LLMs) and Graph Neural Networks (GNNs) to produce parallel
code. has two main modules: parallelism discovery and parallel code
generation. uses Graph Neural Network (GNN) to model flow-aware information,
i.e., data-, control- flow, and call graphs. Once a parallelism opportunity is
identified, a GNN-guided prompt is engineered using GNN’s results to generate
parallel code with the help of an LLM. Due to the nature of OpenMP constructs,
sometimes the order is important in the predictions, and sometimes not. To
better measure the quality of generated OpenMP constructs we provide a new
metric in this paper called OMPScore. Our experimental results show that the
enhanced designed prompt helps to unleash the potential power of LLMs in
generating parallel code out of serial code.

In summary, our paper provides the following key contributions:

  * •

We propose a novel approach, called , leveraging GNNs to guide the automatic
parallelization of code using large language models.

  * •

To the best of our knowledge, is the first automatic parallelization tool
built on top of GNNs and LLMs, having the benefits of both worlds.

  * •

We evaluate the proposed approach on well-established benchmarks such as NAS
Parallel benchmark and Rodinia benchmark.

  * •

We propose a new evaluation measure called OMPScore to assess the quality of
generated OpenMP code.

The format of the paper is as follows: In the next section, we will discuss
the related works. In section 3, motivation examples will be discussed.
Followed by section 4, where our approach is explained in detail along with
the OMPScore. Section 5 presents the experimental results. Section 6 discusses
ablation study and finally, section 7 concludes the paper.

##  2 Related Works

Traditional parallelism assistant tools:  Some traditional tools are based on
static and dynamic analysis for automatic parallelization of sequentially
written programs. PLuTo (Bondhugula et al., 2008) analyzes code statically and
can optimize programs for parallel execution. It is a polyhedral source code
optimizer based on OpenMP (Meadows, 2007). Rose (Quinlan & Liao, 2011) is
another static source-to-source compiler infrastructure that also supports
automatic parallelization using OpenMP. Both of these tools do not require or
use code runtime information while generating parallel counterparts of
sequential programs. DiscoPoP (Li et al., 2016) is a dynamic analysis-based
parallelism assistant tool. It uses dynamic control-flow analysis and data-
dependence profiling for identifying parallel regions in source programs.
However, these traditional analysis-based tools have some drawbacks, as
pointed out by Chen et al. (2023a), and they miss a lot of parallelism
opportunities due to being overly conservative.

Data-driven approaches:  With the significant progress in the field of machine
learning and deep learning, many have proposed automatic data-driven
approaches to identify parallelism opportunities and suggest appropriate
constructs. Chen et al. (2023a) has proposed an approach based on graph neural
networks and augmented Abstract Syntax Trees (ASTs) to identify parallel
loops. Their results show that their GNN-based approach outperforms PragFormer
(Harel et al., ), which uses Transformers (Vaswani et al., 2017) to discover
parallelism opportunities in code. Shen et al. (2021) uses contextual flow
graphs with graph convolution neural networks (Kipf & Welling, 2016) to detect
parallelism. (Shen et al., 2023) uses a combination of control flow, data
flow, and abstract syntax tree to predict parallelism. Even though there has
been some progress in adapting machine learning techniques to predict
parallelism opportunities, little effort has been applied to connect
parallelism detection and code generation. In this work, we address this gap.
We connect GNNs and LLMs to not only discover parallelism but also generate
parallel code. Connecting GNNs to LLMs has been investigated recently (Ghosh
et al., 2022; Chen et al., 2023b). However, to the best of our knowledge, we
are the first to leverage the result of GNN to guide LLM to generate parallel
code out of serial code.

Metrics for Translation Evaluation:  The BLEU score (Papineni et al., 2002) is
a classical metric for evaluating textual similarity in machine translation.
It assesses the overlap between sequences of consecutive $n$ words, called
n-grams. Meteor (Banerjee & Lavie, 2005) was introduced to address some of the
limitations of the BLEU score, such as its tendency to underestimate high-
order n-grams. ROUGE (Lin, 2004) encompasses a set of metrics that evaluate
various aspects of textual similarity. To evaluate code generation, recent
works have introduced metrics like CodeBLEU (Ren et al., 2020) and
CodeBERTScore (Zhou et al., 2023). However, none of these metrics have been
specifically designed for evaluating the quality of OpenMP constructs in terms
of textual similarity.

##  3 Motivation

Listing 1: Reduction loop taken from IS application of NAS Parallel Benchmark

⬇

for (i = 1; i <= 23; i += 1)

{

R23 = 0.50 * R23;

T23 = 2.0 * T23;

}

The remarkable growth of Large Language Models (LLMs) has led us to use them
in a variety of fields. Although LLMs are powerful in Question Answering
tasks, sometimes they struggle to generate quality responses for tasks
requiring domain-specific knowledge. For example, for the task of parallelism
discovery, if LLMs are invoked with basic prompts without any background
information, very often they can not generate satisfactory results. For
example, the code shown in Listing 1 is a parallel loop with a reduction
pattern, and it has two reduction variables, R23 and T23. The correct way to
parallelize the loop is to add a reduction clause with those two variables.
Both GPT-3.5 and GPT-4 recognize the loop as parallel, but they fail to detect
the reduction clause with proper variables. CodeLlama-34B identifies it
wrongly as a non-parallel loop. CodeGen-16B detects it as a parallel loop but
wrongly identifies the reduction variables as private variables. The loop in
Listing 2 is non-parallel due to having inter-iteration dependencies. However,
when the LLMs: GPT-3.5, GPT-4, and CodeGen-16B were prompted about whether
this loop could be parallelized using OpenMP or not, all three LLMs wrongly
parallelized the loop by adding the #pragma omp parallel for clause except for
CodeLlama-34B. The loop in Listing 3 is a parallel loop that is recommended to
be parallelized using the private clause, as the variable i needs to be
private to each thread. Although loop counters are considered private by
default, usually common practice is to add private clause explicitly to the
loop. However, all four LLMs identify the parallel loop but do not add the
private clause for variable i, and when we checked the ground truth value for
this loop, we found that the developers added the private clause to variable
i. All these examples show that in spite of being extremely powerful, LLMs can
fail to generate proper parallel codes even for quite simple cases. However,
the performance of the LLMs can be improved if the LLMs are given some
background information regarding the loop prior to generating parallel codes.
That is what motivated us to develop , which improves the performance of LLMs
by providing them GNN-based guidance.

Listing 2: Non-parallel loop taken from MG Application of NAS Parallel
Benchmark

⬇

for (i1 = d1; i1 <= mm1 - 1; i1 += 1)

{

u[2*i3-t3-1][2*i2-t2-1][2*i1-d1-1] =

u[2*i3-t3-1][2*i2-t2-1][2*i1-d1-1] \+

0.25 * (z[i3][i2][i1-1] \+

z[i3][i2-1][i1-1] + z[i3-1][i2][i1-1] \+

z[i3-1][i2-1][i1-1]);

}

Listing 3: Private loop taken from Heartwall Application of Rodinia-3.1
Benchmark

⬇

for (i = public.endoPoints;

i <= public.allPoints-1; i += 1) {

private[i].point_no = i - public.endoPoints;

private[i].in_pointer =

private[i].point_no * public.in_mod_elem;

private[i].d_Row = public.d_epiRow;

private[i].d_Col = public.d_epiCol;

private[i].d_tRowLoc = public.d_tEpiRowLoc;

private[i].d_tColLoc = public.d_tEpiColLoc;

private[i].d_T = public.d_epiT;

}

##  4 Approach

In this section, we present . An approach that leverages Graph Neural Network
to learn the flow-aware characteristics of the programs, such as control flow,
data flow, and call flow, to guide LLMs to better generate parallel code by
constructing a GNN-guided OMP prompt. Figure 1 shows the overall workflow of .
Figure 1(a) shows the training process where we train a GNN model to predict
parallelism opportunity as well as the parallel pattern. Figure 1(b) shows
that at inference time, GNN is used to create a GNN-guided OMP prompt for the
LLM to generate parallel code.

(a) Training

(b) Inference

Figure 1: Overview of the AutoParLLM workflow.

###  4.1 Training

The first step in our approach is training a Graph Neural Network to learn the
features of the input programs.

Data Collection and Preprocessing: First, we collect data to train our neural
network to detect parallelism and patterns. We want our neural network model
to be able to realize if a region of a code (such as a loop) is parallelizable
or not (for example, due to loop iteration dependency). We use the OMP_Serial
dataset (Chen et al., 2023a) for this purpose. Also, some pre-processing is
applied to transform the dataset to graph representation of programs so that
our GNN-based models can learn efficiently from the representation. The
Experimental Results section provides more details regarding the dataset and
preprocessing.

Program Representation:  While different program representations can be used
to train neural networks, we use PerfoGraph (TehraniJamsaz et al., 2023)
program representation in this work. PerfoGraph has the advantages of ProGraML
(Cummins et al., 2020). Moreover, it can also represent multi-dimensional
arrays and vectors in the programs. Additionally, it is numerically aware,
meaning it can encode numbers. Experiments that have been conducted on
PerfoGraph, show that this representation is effective for the task of
parallelism discovery and pattern detection (TehraniJamsaz et al., 2023).

Graph Neural Network Training: In our experiments, we realized it is
challenging for Transformer models to easily detect parallel regions or
patterns. In the motivation section, we saw that LLMs sometimes can not detect
loop dependencies and generate the parallel version of the code where they are
not supposed to. Using the PerfoGraph representation, we train a Graph Neural
Network (GNN) to specifically learn the flow-aware features of the programs.
Then, we use our GNN model to predict the parallel regions and patterns. Since
there are three types of flow in our program representation, we adapt
Heterogeneous Relational Graph Convolution to model and learn each flow in the
graph representation.

###  4.2 Inference

In this part, we explain how we utilize the results of our GNN model to guide
the LLM model to generate appropriate parallel code.

Prompt Engineering: In the first step, before even constructing the prompt for
the LLM, we first use GNN model to identify if there is a parallelism
opportunity in the given code. If there is no parallelism opportunity, the
parallel version of the given code will not be generated. This is an important
step, as later in the result section, we will see that some LLMs have
difficulties identifying the cases where they should not generate parallel
code. Figure 3 shows the GNN-guided OMP prompt which is used to generate
parallel OpenMP code. As said, the prompt would be used only if our GNN model
predicts a parallelization opportunity. Thereafter, the corresponding patterns
will be predicted by the GNN as well. The supported patterns at the moment
are: do-all, private, reduction, and reduction and private together.
Therefore, the clause placeholder in the prompt will be replaced by the name
of the predicted pattern.

Act as a C++ OpenMP Parallelization Tool. You will be given a code. Your task
is to parallelize the code using OpenMP. You can add any OpenMP clauses if
necessary. If the code is not parallalizable, output the original given
code.\n Code: {code}\n Output code:

Figure 2: Basic OMP Prompt to generate OpenMP Code

Moreover, we also designed a basic OMP prompt by removing the GNN part of our
approach altogether. Figure 2 shows the basic OMP prompt template. It is worth
noting that since GNN is not utilized for the basic prompt, whether the code
is parallelizable or what kind of pattern exists in the code is delegated to
the LLM model itself.

Act as a C++ OpenMP Parallelization Tool. You will be given a code. Your task
is to parallelize the code using OpenMP and only output the code. Add {clause}
to the loop.\n Code: {code}\n Output Code:

Figure 3: GNN-guided OMP Prompt

The choice of LLM depends on the user’s preference. Later, in the experimental
result section, we will see the results of four different LLMs. Lastly, some
LLMs follow a specific prompt template, so our OMP or GNN-guided OMP prompts
will be updated to follow the LLM-specific prompt template. For example,
Figure 4 shows the GNN-guided OMP prompt template that is used for CodeLlama
(Rozière et al., 2023).

<s>[INST] <<SYS>> Act as a C++ OpenMP Parallelization Tool. You will be given
a code. Your task is to parallelize the code using OpenMP and only output the
code. Add {clause} to the loop. <</SYS>>\n\n Code: {code}\n Output Code:
[/INST]

Figure 4: GNN-guided OMP prompt for CodeLlama

###  4.3 OMPScore

Figure 5: Overview of OMPScore.

Some characteristics of OpenMP directives and clauses challenge the evaluation
using existing textual similarity metrics. To illustrate, consider Figure 5,
where we have a candidate and a reference directive, each composed of multiple
clauses. One characteristic pertains to the order of variables or operands
within certain clauses, where variable rearrangements may not alter semantic
meaning (e.g., private(k,j,i) is equivalent to private(j,i,k)). Another
characteristic involves specific clause types where the order of elements
significantly affects directive performance. For example, in Figure 5, the
candidate directive’s reduction(z:+) clause is considered a mismatch to the
reference directive. In essence, OpenMP directives encompass both order-
sensitive and order-insensitive clauses, making a uniform treatment of all
clauses as either order-sensitive or order-insensitive inadequate for accurate
scoring.

We introduce OMPScore, a metric that enhances Rouge-L score evaluation for
OpenMP directives through a combination of regular expressions and program
analysis. OMPScore comprises four key modules designed to preprocess input,
both candidate and reference directives, to provide improved arguments for
Rouge-L score. In the initial stage, the Masking module detects potential
clauses or directives for updating. It does so by identifying clauses within
OpenMP directives using regular expressions initiated by OpenMP keywords
(e.g., private, shared, or reduction) followed by open/close parentheses.
Subsequently, the second module categorizes all identified masked spans based
on the first word within each span, thereby determining the clause type (e.g.,
private, shared, or reduction). In the third module, we update the clauses
considering two factors related to element order within OpenMP clauses. For
instance, the private clause in the directive undergoes a sorting action while
the reduction clause remains unchanged. To determine whether specific clause
types are order-sensitive or order-insensitive, we refer to the official
OpenMP documentation and
articles111https://www.openmp.org/resources/tutorials-articles/. For order-
insensitive clause types, like the private clause, we alphabetically sort the
elements within their respective element lists. Finally, in the fourth module,
the updated candidate and reference directives serve as input for the Rouge-L
scoring function, yielding the OMPScore, which quantifies the similarity
between the candidate and reference directives.

##  5 Experimental Results

We evaluate the effectiveness of on several applications. In this section, we
describe the details of those experiments. Also, we describe the components of
in detail.

###  5.1 Experimental Setup

We use the OMP_Serial dataset (Chen et al., 2023a) to pre-train the
parallelism discovery and pattern detection module of . The first step is to
train our parallelism detection model to identify whether a region, such as a
loop, can be executed in a parallel manner. The OMP_Serial dataset contains
around 6k compilable C source files that are crawled from Github and well-
known benchmarks like PolyBench (Pouchet & Yuki, 2017), Starbench (Andersch et
al., 2013), BOTS (Duran et al., 2009), and the NAS Parallel Benchmark (Jin et
al., 1999). However, since we use NAS Parallel Benchmark for evaluating the
generated parallel codes, we carefully exclude all samples of NAS Parallel
Benchmark from the dataset for our pre-training phase so that our model does
not ”see” those samples beforehand. After excluding those files, LLVM
Intermediate Representation (LLVM IR) of source C files is generated. To
augment the dataset and increase the size of training data, we compile
programs using different LLVM optimization flags following the approach of
TehraniJamsaz et al. (2022). Ultimately, we have around 10k IR files (6041
parallel, 4194 non-parallel).

The OMP_Serial dataset also contains 200 “private” and 200 “reduction” loops.
However, after removing samples taken directly from NAS benchmark and
extracted templates, around “158” private and “137” reduction samples are
left. Finally, we apply LLVM optimization flags similarly as mentioned above
and generate around 4k IR files (2160 private, 2100 reduction). The “private”
clause detection model determines the need for a “private” clause. Similarly,
the ”reduction” clause detection model is used to identify whether we need a
“reduction” clause in the OpenMP directive or not. For training “private”
clause detection model, two classes are created: private (2160 files) and non-
private (contains 2000 files, 50% of those are taken randomly from “reduction”
and 50% of those are randomly taken from “non-parallel”). Similarly, for
training “reduction” clause detection model, two classes are created:
reduction (2100 files) and non-reduction (contains 2000 files, 50% of those
are taken randomly from “private” and 50% of those are randomly taken from
“non-parallel”). These two models make up the parallel pattern detection
module of .

We use the DGL-based (Wang, 2019) implementation of RGCN (Schlichtkrull et
al., 2018) with 6 GraphConv layers for all three GNN models. Each source
program is a heterogeneous graph represented by PerfoGraph (TehraniJamsaz et
al., 2023), so the HeteroGraphConv module in each layer is used with the ‘sum’
aggregation function. We experimented with different hidden layer sizes and
learning rates and finally used 64 as the hidden layer size and set the
learning rate to 0.01. Each node of the heterogeneous PerfoGraph is embedded
to a 120-dimensional vector. So, the input layer size is set to 120. The
output layer size is set to the number of classes, which is 2, as all three of
the GNN models do binary classification. For graph-level prediction, the
‘mean’ aggregation function combines the results of different node types, and
finally linear classifier is used in the last layer of our RGCN model. The
linear classifier produce a probability score for each class. The model is
trained for 120 epochs, and the checkpoint with the highest validation
accuracy is saved for later inference.

For inference, the three pre-trained models are applied sequentially. First,
the input code is passed to the parallelism detection model. If it classifies
a loop as parallel, then it is passed to the “private” clause detection model.
If the second model classifies it as a “private” loop, then the ”private”
clause is added to the OMP prompt. Finally, the loop is passed to the
“reduction” clause detection model, and similarly, if it classifies the loop
as a “reduction” loop, the “reduction” clause is also added to the OMP prompt.

After creating the GNN-guided OMP prompts, the LLMs are invoked to generate
the parallel counterpart of the sequential programs. We use four LLMs to
demonstrate the performance of ; note that for the LLMs, the temperature
parameter is set to zero to make the models deterministic in predicting the
OpenMP constructs. We also compare with traditional tools like autoPar and
DiscoPoP. However, due to space limitations, we describe those comparisons in
the Appendix. We evaluate the performance of on 11 applications of two
benchmarks: NAS Parallel Benchmark and Rodinia Benchmark(Che et al., 2009).
These applications are developed targeting HPC platforms and heterogeneous
computing. Also, both of the benchmarks have OpenMP annotated loops and their
sequential version from experienced developers.

###  5.2 Evaluating Code Generation on NAS Parallel Benchmark

First, we evaluate on NAS Parallel Benchmark. We extract loops containing
OpenMP pragmas from the eight applications. For extracting loops, we first
annotate the loops using the Rose outlining tool (Quinlan & Liao, 2011). Then,
we compile and generate the IR for the outlined code. Finally, the llvm-
extract command is used to extract the loop-specific IR from the full IR. We
extracted a total of 454 loops (private: 264, reduction: 17, non-parallel
173). We use 80% of the loops to fine-tune our pretrained GNN models. We train
the GNN models in a similar manner described above for 120 epochs. Then we use
20% of loops (90 loops) for evaluating . Of those 90 loops, 58 are parallel,
with 56 loops having ”private” clause and 2 loops having ”reduction” clause.
The rest 32 loops are non-parallel. achieves 94.44% accuracy in parallelism
discovery by correctly predicting 55 out of 58 parallel loops and 30 out of 32
non-parallel loops. Also, correctly detects 52 out of 56 loops with ”private”
clause, and it correctly detected all two loops with ”reduction” clause.

In Table 1, we compare the performance of the codes generated by using the
basic OMP prompt and GNN-guided OMP prompt (denoted as -LLM-name in all
tables). We use different score metrics as well as OMPScore for the
comparison, and it can be observed that our approach improves all LLMs in
terms of these scores.

Table 1: Results on NAS Parallel Benchmark Suite (higher indicates better)

Model | BLEU | CodeBLEU | Rogue-L | METEOR | CodeBERTScore | OMPScore
---|---|---|---|---|---|---
CodeGen-16B | 15.82 | 40.99 | 43.84 | 27.87 | 72.8 | 48.97
-CodeGen-16B | 32.69 | 49.51 | 66.60 | 42.28 | 83.8 | 65.3
GPT-3.5 | 27.11 | 52.57 | 42.83 | 35.16 | 72.3 | 41
-GPT-3.5 | 38.83 | 65.24 | 91.70 | 55.09 | 96.4 | 95.15
GPT-4 | 26.15 | 54.81 | 43.34 | 36.96 | 73.8 | 46.4
-GPT-4 | 40.12 | 68.24 | 90.40 | 55.68 | 95.2 | 95.15
CodeLlama-34B | 26.44 | 53.48 | 45.15 | 36.40 | 74.0 | 45.44
-CodeLlama-34B | 36.14 | 64.81 | 90.59 | 54.86 | 96.0 | 94.46

Table 2: Application-wise execution results (in seconds) on NAS Parallel
Benchmark Suite

Model | BT | IS | CG | FT | LU | MG | SP | Avg. Speedup (%)
---|---|---|---|---|---|---|---|---
GPT-3.5 | 73.560 | 1.138 | 0.822 | 2.270 | 37.665 | 1.080 | 34.163 |
-GPT-3.5 | 71.946 | 1.092 | 0.828 | 2.260 | 37.398 | 1.090 | 30.648 | 2.5%
GPT-4 | 73.424 | 1.136 | 0.882 | 2.250 | 37.445 | 1.090 | 33.648 |
-GPT-4 | 71.892 | 1.087 | 0.880 | 2.244 | 37.052 | 1.080 | 29.322 | 3.4%
CodeLlama-34B | 72.620 | 1.230 | 0.872 | 2.257 | 37.676 | 1.090 | 33.336 |
-CodeLlama-34B | 71.730 | 1.144 | 0.880 | 2.258 | 35.167 | 1.080 | 31.345 | 3.2%
CodeGen-16B | 101.036 | 1.261 | 0.914 | 2.280 | 44.536 | 1.110 | 46.776 |
-CodeGen-16B | 96.760 | 1.173 | 0.882 | 2.260 | 46.040 | 1.100 | 42.640 | 3.4%

Apart from the metric scores, we also evaluate the performance of the
generated codes by measuring their execution time. We execute an application
if at least one loop from that application belongs to our test set of 90
loops. Out of 8 applications, seven applications have at least one loop in the
test set. Only EP application has all its loops in the training set. So, we
exclude EP from the execution. For all other seven applications, we replace
the sequential loops in the testing set with the parallel loops generated
using both regular LLMs and augmented LLMs and then execute the application to
measure execution time. We generate the execution time by executing each
application five times and then report the average execution time. We use the
following formula to calculate the percentage of speedup improvement of
augmented LLM generated codes with respect to codes generated by regular LLMs.

$Speedup\%=(\frac{Execution\\_time\\_LLM-
basic}{Execution\\_time\\_\ourtool\\_augmented\\_LLM}-1)*100$

We calculate the percentage of speedup for every application and then report
the average speedup for all applications in Table 2. Bold fonts show better
runtime. It can be observed that codes generated with guidance have 1.9%
better runtime than GPT-3.5, 2.6% better runtime than GPT-4, 2.9% better
runtime than CodeLlama-34B and 1.4% better runtime than CodeGen-16B in average
across all applications in NAS Parallel Benchmark. All experiments are
performed on computing nodes with the same configuration. Each computing node
has an Intel Xeon Gold 6244 CPU with 32 cores and 366 GB of RAM.

####  5.2.1 Results on Rodinia Benchmark

We further apply on four applications of Rodinia Benchmark that our GNN models
have not seen at all. These applications are developed targeting heterogeneous
computing. We extracted 15 loops from these applications using the method
described earlier. Out of these 15 loops, 12 loops contain the ”private”
clause, and three loops contain the ”reduction” clause. Then we apply to
detect parallelism and pattern of these 15 loops. Out of the 15 loops, is able
to correctly detect and classify all the 12 loops with ”private” clauses and
three loops with ”reduction” clauses. As already described in the NAS
Benchmark experiments, we create the GNN-guided prompts after generating the
predictions. Then, the LLMs are invoked with the GNN-guided prompts to
generate the parallel codes based on the patterns. After generating the
parallel code, we evaluate the quality of the codes generated by both basic
prompt LLMs and in terms of the metrics score as well as our proposed
OMPScore. Table 3 shows the results. We can see that guidance results in a
better code generation. We also see that has a significantly higher OMPScore
for this dataset, too. We also evaluate the runtimes of augmented LLM
generated code with regular LLM generated code for this dataset. The runtimes
are calculated similarly by executing each application five times and then
taking the average on the same computing environments. Table 4 shows the
results. The bold fonts show the better runtime. It can be observed that for
all applications, codes generated with guidance have better runtimes than the
ones generated by basic LLMs. We also calculate the speedup(%) using the same
formula introduced earlier. We can see that our augmented LLM generated codes
have 1.9%, 2.6%, 2.9%, and 1.4% better runtimes than GPT-3.5, GPT-4,
CodeLlama-34B and CodeGen-16B, respectively.

Table 3: Results on Rodinia-3.1 Benchmark Suite (higher indicates better)

Model | BLEU | CodeBLEU | Rogue-L | METEOR | CodeBERTScore | OMPScore
---|---|---|---|---|---|---
CodeGen-16B | 29.87 | 62.34 | 48.57 | 48.19 | 79.0 | 52.88
-CodeGen-16B | 36.93 | 62.77 | 58.67 | 59.97 | 82.2 | 64.57
GPT-3.5 | 56.60 | 81.84 | 75.38 | 71.89 | 91.0 | 79.37
-GPT-3.5 | 71.51 | 89.06 | 91.39 | 85.25 | 97.6 | 98.1
GPT-4 | 55.19 | 81.61 | 76.19 | 70.33 | 91.2 | 79.37
-GPT-4 | 74.83 | 88.03 | 91.39 | 89.58 | 98.6 | 98.1
CodeLlama-34B | 50.08 | 67.82 | 63.50 | 63.07 | 85.9 | 69.55
-CodeLlama-34B | 68.47 | 83.98 | 88.44 | 77.90 | 96.4 | 95.27

Table 4: Application-wise execution results (in seconds) on Rodinia Benchmark
Suite

Model | BFS | B+Tree | Heartwall | 3D | Avg. Speedup (%)
---|---|---|---|---|---
GPT-3.5 | 0.175 | 3.934 | 609.809 | 10.327 |
-GPT3.5 | 0.169 | 3.814 | 603.940 | 10.294 | 1.9%
GPT-4 | 0.173 | 3.931 | 607.527 | 10.309 |
-GPT-4 | 0.162 | 3.822 | 603.93 | 10.281 | 2.6%
CodeLlama-34B | 0.176 | 3.936 | 607.034 | 10.339 |
-CodeLlama-34B | 0.163 | 3.832 | 603.450 | 10.326 | 2.9%
CodeGen-16B | 0.176 | 3.938 | 611.284 | 10.432 |
-CodeGen-16B | 0.174 | 3.836 | 606.492 | 10.349 | 1.4%

###  5.3 Human Evaluation Results

For human judgment score we hired two software developers, each boasting over
five years of experience in working with OpenMP, meticulously review both the
actual and predicted directives generated by each model. For each data point,
they allocate scores ranging from 0 (indicative of the lowest quality) to 5
(indicative of the highest quality) to the predicted directive based on the
number of operations needed to transform the predicted directive into the
actual directive. Each modification operation results in a deduction of 1
point from the judgment score. Subsequently, the two evaluators engage in
discussions to reconcile their assessments and reach a consensus on the final
human judgment scores. Secondly, we gauge the correlation between the metrics
and human judgment scores using the Spearman ranking (Myers & Sirois, 2004).
Specifically, we employ the directives generated using AutoParLLM-GPT-4 with
the NAS Parallel Benchmark (NPB) for our human judgement, and the average
human score for this set is 4.72. The outcomes of this experiment can be
observed in Table 5. Notably, OMPScore achieved the highest correlation with
human judgment, reaching up to an impressive 99.99%. This significantly
surpasses other existing metrics, exceeding their correlations by up to
fourfold. Our evaluation highlights that even the optimized version of the
BLEU score like the CodeBLEU (Ren et al., 2020) exhibited the lowest
correlation with human judgment. These findings underscore the effectiveness
of OpenMPScore over existing metrics when it comes to evaluating OpenMP
directives.

Table 5: Comparison of the Spearman Correlation between original metrics and
their corresponding metrics provided by OMPScore on the results of NPB
benchmark with AutoParLLM-GPT-4

Correlation | BLEU | CodeBLEU | Rouge-L | Meteor | CodeBERTScore | OMPScore
---|---|---|---|---|---|---
Spearman | 24.45 | 28.06 | 61.04 | 24.01 | 48.72 | 99.99

##  6 Ablation Study

In this section, we discuss the difference between the parallel versions of
the loops generated using basic OMP prompt and using . The generated code of
GPT-3.5 and GPT-4 for Listing 1 before and after applying the guidance are
shown in Listing 4 and 5 respectively. We can see the latter code generated
with is properly decorated with ”reduction” clause however without both LLMs
fail to add the ”reduction” clause.

Listing 4: Listing 1 parallelized by GPT-3.5 and GPT-4

⬇

#pragma omp parallel for

for (i = 1; i <= 23; i += 1){

R23 = 0.50 * R23; T23 = 2.0 * T23; }

Listing 5: Listing 1 parallelized by GPT-3.5 and GPT-4 after applying guidance

⬇

#pragma omp parallel for reduction(*:, R23, T23)

for (i = 1; i <= 23; i += 1){

R23 = 0.50 * R23; T23 = 2.0 * T23; }

Also, the non-parallel loop in Listing 2 which was wrongly classified as
parallel loop by GPT-3.5, GPT-4, CodeGen-16B can correctly classify the loop
as non-parallel with the guidance from . The private loop in Listing 3 is also
properly parallelized using the ”private” clause by all four LLMs after
guidance is applied as can be seen in Listing 6 and 7 which also matches with
the clause added by developers. So, all three loops in the Motivation section
are successfully parallelized using our GNN-enhanced prompt-based approach by
mitigating the shortcomings of regular LLMs.

Listing 6: Listing 3 parallelized by GPT-3.5, GPT-4, CodeLlama-34B and
CodeGen-16B

⬇

#pragma omp parallel for

for (i = public.endoPoints;

i <= public.allPoints-1; i += 1) {

private[i].point_no = i - public.endoPoints;

//rest of the code }

Listing 7: Listing 3 parallelized by all four LLMs after applying guidance

⬇

#pragma omp parallel for private (i)

for (i = public.endoPoints;

i <= public.allPoints-1; i += 1) {

private[i].point_no = i - public.endoPoints;

//rest of the code }

##  7 Conclusion and Future Direction

In this paper, we presented . is an approach built on top of GNNs and LLMs to
enable automatic parallelization of programs via inserting OpenMP constructs.
The key idea of is that it leverages GNNs to learn control flow and data flow
and steers the code generation of LLMs to add appropriate and necessary OpenMP
constructs through a specially designed prompt called GNN-guided OMP prompt.
Experimental results indicate that the proposed approach is indeed effective,
and without GNN guidance, LLM models could produce erroneous or inefficient
parallel code. We have plans to extend the approach further to support more
types of patterns. Moreover, one interesting extension of our approach is to
include some auto-tuning information in our prompt by training the GNN further
to predict the number of threads for example, or the loop scheduling types.

#### Acknowledgments

We express our gratitude to Intel Labs, Santa Clara, CA, for their generous
support of this project. Also, we thank Akash Dutta, PhD student, Dept. of
Computer Science at Iowa State University for his guidance and assistance for
using Rose outliner. We also thank the Iowa State University ResearchIT Unit
(https://researchit.las.iastate.edu/) for computational support and
assistance.

## References

  * Andersch et al. (2013) Michael Andersch, Ben Juurlink, and C Chi.  A benchmark suite for evaluating parallel programming models.  In _Proceedings of Workshop on Parallel Systems and Algorithms (PARS)_ , volume 28, pp. 1–6, 2013.
  * Banerjee & Lavie (2005) Satanjeev Banerjee and Alon Lavie.  Meteor: An automatic metric for mt evaluation with improved correlation with human judgments.  In _Proceedings of the acl workshop on intrinsic and extrinsic evaluation measures for machine translation and/or summarization_ , pp. 65–72, 2005.
  * Bondhugula et al. (2008) Uday Bondhugula, Albert Hartono, J Ramanujam, and P Sadayappan.  Pluto: A practical and fully automatic polyhedral program optimization system.  In _Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation (PLDI 08), Tucson, AZ (June 2008)_. Citeseer, 2008.
  * Che et al. (2009) Shuai Che, Michael Boyer, Jiayuan Meng, David Tarjan, Jeremy W Sheaffer, Sang-Ha Lee, and Kevin Skadron.  Rodinia: A benchmark suite for heterogeneous computing.  In _2009 IEEE international symposium on workload characterization (IISWC)_ , pp. 44–54. Ieee, 2009.
  * Chen et al. (2023a) Le Chen, Quazi Ishtiaque Mahmud, Hung Phan, Nesreen Ahmed, and Ali Jannesari.  Learning to parallelize with openmp by augmented heterogeneous ast representation.  _Proceedings of Machine Learning and Systems_ , 5, 2023a.
  * Chen et al. (2023b) Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al.  Exploring the potential of large language models (llms) in learning on graphs.  _arXiv preprint arXiv:2307.03393_ , 2023b.
  * Cummins et al. (2020) Chris Cummins, Zacharias V Fisches, Tal Ben-Nun, Torsten Hoefler, and Hugh Leather.  Programl: Graph-based deep learning for program optimization and analysis.  _arXiv preprint arXiv:2003.10536_ , 2020.
  * Duran et al. (2009) Alejandro Duran, Xavier Teruel, Roger Ferrer, Xavier Martorell, and Eduard Ayguade.  Barcelona openmp tasks suite: A set of benchmarks targeting the exploitation of task parallelism in openmp.  In _2009 international conference on parallel processing_ , pp. 124–131. IEEE, 2009.
  * Ghosh et al. (2022) Samujjwal Ghosh, Subhadeep Maji, and Maunendra Sankar Desarkar.  Graph neural network enhanced language models for efficient multilingual text classification.  _arXiv preprint arXiv:2203.02912_ , 2022.
  * Harel et al. (2023) Re’em Harel, Yuval Pinter, and Gal Oren.  Learning to parallelize in a shared-memory environment with transformers.  In _Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming_ , pp. 450–452, 2023.
  * (11) Re’em Harel, Yuval Pinter, and Gal Oren.  Learning to parallelize source code via openmp with transformers.
  * Jin et al. (1999) Hao-Qiang Jin, Michael Frumkin, and Jerry Yan.  The openmp implementation of nas parallel benchmarks and its performance.  1999\.
  * Kadosh et al. (2023) Tal Kadosh, Nadav Schneider, Niranjan Hasabnis, Timothy Mattson, Yuval Pinter, and Gal Oren.  Advising openmp parallelization via a graph-based approach with transformers.  _arXiv preprint arXiv:2305.11999_ , 2023.
  * Kipf & Welling (2016) Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016.
  * Li et al. (2015) Zhen Li, Rohit Atre, Zia Ul-Huda, Ali Jannesari, and Felix Wolf.  Discopop: A profiling tool to identify parallelization opportunities.  In _Tools for High Performance Computing 2014: Proceedings of the 8th International Workshop on Parallel Tools for High Performance Computing, October 2014, HLRS, Stuttgart, Germany_ , pp. 37–54. Springer, 2015.
  * Li et al. (2016) Zhen Li, Rohit Atre, Zia Huda, Ali Jannesari, and Felix Wolf.  Unveiling parallelization opportunities in sequential programs.  _Journal of Systems and Software_ , 117:282–295, 2016.
  * Lin (2004) Chin-Yew Lin.  Rouge: A package for automatic evaluation of summaries.  In _Text summarization branches out_ , pp. 74–81, 2004.
  * Meadows (2007) Larry Meadows.  Openmp 3.0–a preview of the upcoming standard.  In _High Performance Computing and Communications: Third International Conference, HPCC 2007, Houston, USA, September 26-28, 2007. Proceedings 3_ , pp. 4–4. Springer, 2007.
  * Myers & Sirois (2004) Leann Myers and Maria J Sirois.  Spearman correlation coefficients, differences between.  _Encyclopedia of statistical sciences_ , 12, 2004.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu.  Bleu: A method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting on Association for Computational Linguistics_ , ACL ’02, pp. 311–318, USA, 2002. Association for Computational Linguistics.  doi: 10.3115/1073083.1073135.  URL https://doi.org/10.3115/1073083.1073135.
  * Pouchet & Yuki (2017) Louis-Noël Pouchet and Tomofumi Yuki.  Polybench: The polyhedral benchmark suite (version 4.2), 2017.
  * Quinlan & Liao (2011) Dan Quinlan and Chunhua Liao.  The ROSE source-to-source compiler infrastructure.  In _Cetus users and compiler infrastructure workshop, in conjunction with PACT_ , volume 2011, pp. 1. Citeseer, 2011.
  * Ren et al. (2020) Shuo Ren, Daya Guo, Shuai Lu, Long Zhou, Shujie Liu, Duyu Tang, Neel Sundaresan, Ming Zhou, Ambrosio Blanco, and Shuai Ma.  Codebleu: a method for automatic evaluation of code synthesis, 2020.
  * Rozière et al. (2023) Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, et al.  Code llama: Open foundation models for code.  _arXiv preprint arXiv:2308.12950_ , 2023.
  * Schlichtkrull et al. (2018) Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling.  Modeling relational data with graph convolutional networks.  In _The Semantic Web: 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3–7, 2018, Proceedings 15_ , pp. 593–607. Springer, 2018.
  * Shen et al. (2021) Yuanyuan Shen, Manman Peng, Shiling Wang, and Qiang Wu.  Towards parallelism detection of sequential programs with graph neural network.  _Future Generation Computer Systems_ , 125:515–525, 2021.
  * Shen et al. (2023) Yuanyuan Shen, Manman Peng, Qiang Wu, and Guoqi Xie.  Multigraph learning for parallelism discovery in sequential programs.  _Concurrency and Computation: Practice and Experience_ , 35(9):e7648, 2023.
  * TehraniJamsaz et al. (2022) Ali TehraniJamsaz, Mihail Popov, Akash Dutta, Emmanuelle Saillard, and Ali Jannesari.  Learning intermediate representations using graph neural networks for numa and prefetchers optimization.  In _2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_ , pp. 1206–1216. IEEE, 2022.
  * TehraniJamsaz et al. (2023) Ali TehraniJamsaz, Quazi Ishtiaque Mahmud, Le Chen, Nasreen K Ahmed, and Ali Jannesari.  Perfograph: A numerical aware program graph representation for performance optimization and program analysis.  _arXiv preprint arXiv:2306.00210_ , 2023.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Wang (2019) Minjie Yu Wang.  Deep graph library: Towards efficient and scalable deep learning on graphs.  In _ICLR workshop on representation learning on graphs and manifolds_ , 2019.
  * Zhou et al. (2023) Shuyan Zhou, Uri Alon, Sumit Agarwal, and Graham Neubig.  Codebertscore: Evaluating code generation with pretrained models of code.  2023\.  URL https://arxiv.org/abs/2302.05527.

##  8 Appendix

###  8.1 Comparing with Traditional Tools

We further compare the parallelism discovery of against two popular
parallelization tools: AutoPar and DiscoPoP. AutoPar performs static analysis
to find parallel regions (such as loops), whereas DiscoPoP is a dynamic tool
and it executes the code to identify potential parallel regions. Therefore,
choosing these two tools enable us to compare against both static and dynamic
tools.

We run our GNN-based classifiers to detect the parallel loops in two subsets
of the OMP_Serial dataset. These two subsets are specifically developed to
compare the performance of parallelism detection models against these two
tools, AutoPar and DiscoPoP. The subsets are called AutoPar Subset and
DiscoPoP subset. The performance of AutoPar and DiscoPoP in the subsets are
quoted from TehraniJamsaz et al. (2023). We run the parallelism detection
module of for both of these subsets and report the results in tables 6 and 7 .
It can be observed that is quite good at parallelism discovery and achieves
36% higher accuracy than DiscoPoP and 54% higher accuracy than AutoPar. We can
also see that both traditional tools have very high precision scores. This is
because they are very conservative while detecting parallel loops. Even
though, they have high precision scores they miss out on a considerable number
of parallelism opportunities.

Table 6: Parallelism Discovery on DiscoPoP Subset (Detecting parallel loops) Tool | Precision | Recall | F1-score | Accuracy
---|---|---|---|---
DiscoPoP | 1 | 0.54 | 0.70 | 0.63
| 0.99 | 0.99 | 0.99 | 0.99
Table 7: Parallelism Discovery on autoPar Subset (Detecting parallel loops) Tool | Precision | Recall | F1-score | Accuracy
---|---|---|---|---
autoPar | 1 | 0.14 | 0.20 | 0.38
| 0.93 | 0.92 | 0.92 | 0.92

###  8.2 Details regarding the RGCN model

We used the DGL-based RGCN model. As our RGCN is based on heterogeneous graphs
we used 6 HeteroGraphConv laters. In each HeteroGraphConv layer used ”sum”
aggregation. Relu is used as the activation function. The hidden layer
dimension is set to 64. We train our model on batch size = 100. Also, Adam
optimizer is used. For loss calculation we used the cross entropy loss
function from PyTorch.


={}& \underbrace{- p^{2}(1-p)^{4}(1-p^{2}+3p^{3}-3p^{4}+p^{5})\mu(LD)}_{\text{combining underbraced terms labeled (d)}}\nonumber\\& \underbrace{- p(1-p)^{2}(1-6p+9p^{2}-p^{3}-7p^{4}+11p^{5}-10p^{6}+5p^{7}-p^{8})\mu(LLD)}_{\text{combining underbraced terms labeled (d)}}\nonumber\\& \underbrace{- p(1-p)^{4}(1-3p+p^{2}+p^{3}-3p^{4}+3p^{5}-p^{6})\mu(DLD)}_{\text{combining underbraced terms labeled (d)}} - \beta_{1}\mu(DWLD) - \beta_{2}\mu(LWLD)\nonumber\\
={}& - p^{2}(1-p)^{4}(1-p^{2}+3p^{3}-3p^{4}+p^{5})\mu(LD) - \beta_{3}\mu(LLD) - \beta_{2}\{\mu(DLD)+\mu(LWLD)\} - \beta_{1}\mu(DWLD),\label{intermediate_8}
\end{align}

in which

* the polynomial $\beta_{1}=p(1-p)^{4}(2-5p+2p^{2}+p^{3}-3p^{4}+3p^{5}-p^{6})$ is strictly positive for all $p \in (0,0.505225)$,

* the polynomial $\beta_{2}=p(1-p)^{4}(1-3p+p^{2}+p^{3}-3p^{4}+3p^{5}-p^{6})$ is strictly positive for all $p \in (0,0.387969)$,

* the polynomial $\beta_{3}=p(1-p)^{2}(1-6p+9p^{2}-p^{3}-7p^{4}+11p^{5}-10p^{6}+5p^{7}-p^{8})$ is strictly positive for all $p \in (0,0.265137)$.

Therefore, for $0 < p \leqslant 0.201382$, each $\beta_{i} > 0$. Incorporating (<ref>) and (<ref>) into (<ref>), we obtain

\begin{align}
w_{3}(\F_{p}\mu) ={}& w_{3}(\mu) + (2p-14p^{2}+23p^{3}-14p^{4}+3p^{6}-p^{7})\mu(LD) \underbrace{- p^{2}\mu(LDD)} - p^{2}\mu(DDD) \nonumber\\&- p^{3}(1-p)^{3}(1+p)(2-p)(3-4p+5p^{2}-3p^{3}+p^{4})\mu(LD) \underbrace{- \alpha_{1}\mu(LDL)}\nonumber\\& \underbrace{- \alpha_{2}\mu(LDW)} - \alpha_{3}\{\mu(DLDD)+\mu(LLDD)\} + p^{2}(1-p)^{8}(1-2p)\mu(WWLDL) \nonumber\\&- p^{2}(1-p)^{4}(1-p^{2}+3p^{3}-3p^{4}+p^{5})\mu(LD) - \beta_{3}\mu(LLD) - \beta_{2}\{\mu(DLD)+\mu(LWLD)\} \nonumber\\&- \beta_{1}\mu(DWLD) + p^{4}(1-p)^{8}\mu(WWLDD) - p(1-p)^{6}C_{LLWD} - p(1-p)^{6}C_{LLDW} \nonumber\\& - p^{2}C_{WDD} - p^{2}(3-3p+p^{2})(1-p)^{2}C_{LWD} - C_{3}\nonumber\\
={}& w_{3}(\mu) + (2p-14p^{2}+23p^{3}-14p^{4}+3p^{6}-p^{7})\mu(LD) \underbrace{- p^{2}\mu(LD)} - p^{2}\mu(DDD) \nonumber\\&- p^{3}(1-p)^{3}(1+p)(2-p)(3-4p+5p^{2}-3p^{3}+p^{4})\mu(LD)\nonumber\\& \underbrace{- (1-3p-p^{2}+2p^{3}+13p^{4}-31p^{5}+26p^{6}+p^{7}-28p^{8}+34p^{9}-21p^{10}+7p^{11}-p^{12})\mu(LDL)}\nonumber\\& \underbrace{- p(1-4p-6p^{2}+31p^{3}-46p^{4}+32p^{5}-28p^{7}+34p^{8}-21p^{9}+7p^{10}-p^{11})\mu(LDW)} \nonumber\\&- \alpha_{3}\{\mu(DLDD)+\mu(LLDD)\} + p^{2}(1-p)^{8}(1-2p)\mu(WWLDL) \nonumber\\&- p^{2}(1-p)^{4}(1-p^{2}+3p^{3}-3p^{4}+p^{5})\mu(LD) - \beta_{3}\mu(LLD) - \beta_{2}\{\mu(DLD)+\mu(LWLD)\} \nonumber\\&- \beta_{1}\mu(DWLD) + p^{4}(1-p)^{8}\mu(WWLDD) - p(1-p)^{6}C_{LLWD} - p(1-p)^{6}C_{LLDW} - p^{2}C_{WDD} \nonumber\\&- p^{2}(3-3p+p^{2})(1-p)^{2}C_{LWD} - C_{3}\nonumber\\
{}&(\text{the underbraced terms in the step above are obtained by combining the underbraced terms}\nonumber\\&\text{from the previous step})\nonumber\\
={}& w_{3}(\mu) \underbrace{+ (2p-14p^{2}+23p^{3}-14p^{4}+3p^{6}-p^{7})\mu(LD) - p^{2}\mu(LD)} - p^{2}\mu(DDD) \nonumber\\&\underbrace{- p^{3}(1-p)^{3}(1+p)(2-p)(3-4p+5p^{2}-3p^{3}+p^{4})\mu(LD)} - \gamma_{1}\mu(LDL) - \gamma_{2}\mu(LDW) \nonumber\\&- \alpha_{3}\{\mu(DLDD)+\mu(LLDD)\} \underbrace{- p^{2}(1-p)^{4}(1-p^{2}+3p^{3}-3p^{4}+p^{5})\mu(LD)} \nonumber\\&- \beta_{3}\mu(LLD) - \beta_{2}\mu(DLD) - \beta_{1}\mu(DWLD) - \beta_{2}\mu(LWLD) + p^{4}(1-p)^{8}\mu(WWLDD) \nonumber\\&+ p^{2}(1-p)^{8}(1-2p)\mu(WWLDL) - p(1-p)^{6}C_{LLWD} - p(1-p)^{6}C_{LLDW} - p^{2}C_{WDD} \nonumber\\&- p^{2}(3-3p+p^{2})(1-p)^{2}C_{LWD} - C_{3}\nonumber\\
={}& w_{3}(\mu) \underbrace{+ p(2-16p+21p^{2}+4p^{3}-39p^{4}+50p^{5}-35p^{6}+7p^{7}+13p^{8}-14p^{9}+6p^{10}-p^{11})\mu(LD)} \nonumber\\& - p^{2}\mu(DDD) - \gamma_{1}\mu(LDL) - \gamma_{2}\mu(LDW) - \alpha_{3}\{\mu(DLDD)+\mu(LLDD)\} - \beta_{3}\mu(LLD) - \beta_{2}\{\mu(DLD)\nonumber\\&+\mu(LWLD)\} - \beta_{1}\mu(DWLD) \underbrace{+ p^{4}(1-p)^{8}\mu(WWLDD) + p^{2}(1-p)^{8}(1-2p)\mu(WWLDL)} \nonumber\\&- p(1-p)^{6}C_{LLWD} - p(1-p)^{6}C_{LLDW} - p^{2}C_{WDD} - p^{2}(3-3p+p^{2})(1-p)^{2}C_{LWD} - C_{3}\nonumber\\
{}&(\text{once again, the underbraced terms in the step above are obtained by combining the}\nonumber\\&\text{underbraced terms from the previous step})\label{wt_ineq_3}
\end{align}

* the polynomial $\gamma_{1}=(1-3p-p^{2}+2p^{3}+13p^{4}-31p^{5}+26p^{6}+p^{7}-28p^{8}+34p^{9}-21p^{10}+7p^{11}-p^{12})$ is strictly positive for all $p \in [0,0.345627)$,

* the polynomial $\gamma_{2}=p(1-4p-6p^{2}+31p^{3}-46p^{4}+32p^{5}-28p^{7}+34p^{8}-21p^{9}+7p^{10}-p^{11})$ is strictly positive for all $p \in (0,0.238556)$,

* and the polynomial $p(2-16p+21p^{2}+4p^{3}-39p^{4}+50p^{5}-35p^{6}+7p^{7}+13p^{8}-14p^{9}+6p^{10}-p^{11})$ is strictly negative for all $p > 0.157175$.

Among the problematic terms, indicated by underbraces, in the right side of (<ref>), there is $p^{4}(1-p)^{8}\mu(WWLDD)$, which we now take care of by introducing the adjustment $w_{4}(\mu) = w_{3}(\mu) - \beta_{2}\mu(LWLD)$. Note that $w_{4}(\mu)$, when exanded (by substituting the expression for $w_{3}(\mu)$), becomes exactly the weight function defined in (<ref>).

We partially compute $\F_{p}\mu(LWLD)$, which is the probability of the event $\{\F_{p}\eta(0)=L,\F_{p}\eta(1)=W,\F_{p}\eta(2)=L,\F_{p}\eta(3)=D\}$:

* Suppose $\eta(0)=\eta(1)=W$, $\eta(2)=L$ and $\eta(3)=\eta(4)=D$. Then the event $\{\F_{p}\eta(0)=L\}$ happens with probability $1$, the event $\{\F_{p}\eta(1)=W\}$ happens with probability $(1-p)$, the event $\{\F_{p}\eta(2)=L\}$ happens with probability $p^{2}$, and the event $\{\F_{p}\eta(3)=D\}$ happens with probability $(1-p)(1+p)$. Thus, the contribution of this case to $\F_{p}\mu(LWLD)$ is $p^{2}(1-p)^{2}(1+p)\mu(WWLDD)$.

Therefore, letting $C_{LWLD}$ denote the contribution from the cases not considered above, we obtain

\begin{align}\label{pushforward_LWLD_q=0}
\F_{p}\mu(LWLD) = p^{2}(1-p)^{2}(1+p)\mu(WWWLD) + C_{LWLD}.
\end{align}

Incorporating the new adjustment into (<ref>), and emulating (<ref>), we obtain:

\begin{align}
w_{4}\left(\F_{p}\mu\right) ={}& w_{4}(\mu) + \beta_{2}\mu(LWLD) + p(2-16p+21p^{2}+4p^{3}-39p^{4}+50p^{5}-35p^{6}+7p^{7}+13p^{8}-14p^{9}\nonumber\\&+6p^{10}-p^{11})\mu(LD) - p^{2}\mu(DDD) - \gamma_{1}\mu(LDL) - \gamma_{2}\mu(LDW) - \alpha_{3}\{\mu(DLDD)+\mu(LLDD)\} \nonumber\\&- \beta_{3}\mu(LLD) - \beta_{2}\mu(DLD) - \beta_{1}\mu(DWLD) - \beta_{2}\mu(LWLD) \underbrace{+ p^{4}(1-p)^{8}\mu(WWLDD)} \nonumber\\&+ p^{2}(1-p)^{8}(1-2p)\mu(WWLDL) - p(1-p)^{6}C_{LLWD} - p(1-p)^{6}C_{LLDW} - p^{2}C_{WDD} \nonumber\\&- p^{2}(3-3p+p^{2})(1-p)^{2}C_{LWD} - C_{3} \underbrace{- \beta_{2}p^{2}(1-p)^{2}(1+p)\mu(WWLDD)} - \beta_{2}C_{LWLD}\nonumber\\
={}& w_{4}(\mu) + p(2-16p+20p^{2}+7p^{3}-42p^{4}+51p^{5}-35p^{6}+7p^{7}+13p^{8}-14p^{9}+6p^{10}-p^{11})\nonumber\\&\mu(LD) - p^{2}\mu(DDD) - \gamma_{1}\mu(LDL) - \gamma_{2}\mu(LDW) - \alpha_{3}\{\mu(DLDD)+\mu(LLDD)\} - \beta_{3}\mu(LLD) \nonumber\\&- \beta_{2}\mu(DLD) - \beta_{1}\mu(DWLD) \underbrace{- p^{3}(1-p)^{6}(1-3p+p^{3}-2p^{4}+2p^{6}-p^{7})\mu(WWLDD)}\nonumber\\&+ p^{2}(1-p)^{8}(1-2p)\mu(WWLDL) - p(1-p)^{6}C_{LLWD} - p(1-p)^{6}C_{LLDW} - p^{2}C_{WDD} \nonumber\\&- p^{2}(3-3p+p^{2})(1-p)^{2}C_{LWD} - C_{3} - \beta_{2}C_{LWLD}\nonumber\\
={}& w_{4}(\mu) + p(2-16p+20p^{2}+7p^{3}-42p^{4}+51p^{5}-35p^{6}+7p^{7}+13p^{8}-14p^{9}+6p^{10}-p^{11})\nonumber\\&\mu(LD) - p^{2}\mu(DDD) \underbrace{- \gamma_{1}\mu(LDL)} - \gamma_{2}\mu(LDW) - \alpha_{3}\{\mu(DLDD)+\mu(LLDD)\} - \beta_{3}\mu(LLD) \nonumber\\&- \beta_{2}\mu(DLD) - \beta_{1}\mu(DWLD) - \gamma_{3}\mu(WWLDD) \underbrace{+ p^{2}(1-p)^{8}(1-2p)\mu(WWLDL)}_{\text{use } \mu(WWLDL) \leqslant \mu(LDL) \text{ in the next step}} \nonumber\\&- p(1-p)^{6}C_{LLWD} - p(1-p)^{6}C_{LLDW} - p^{2}C_{WDD} - p^{2}(3-3p+p^{2})(1-p)^{2}C_{LWD} - C_{3} \nonumber\\&- \beta_{2}C_{LWLD}\nonumber\\
\leqslant{}& w_{4}(\mu) + p(2-16p+20p^{2}+7p^{3}-42p^{4}+51p^{5}-35p^{6}+7p^{7}+13p^{8}-14p^{9}+6p^{10}-p^{11})\nonumber\\&\mu(LD) - p^{2}\mu(DDD) \underbrace{- (1-3p-2p^{2}+12p^{3}-31p^{4}+81p^{5}-156p^{6}+197p^{7}-168p^{8}+98p^{9}}\nonumber\\&\underbrace{-38p^{10}+9p^{11}-p^{12})\mu(LDL)} - \gamma_{2}\mu(LDW) - \alpha_{3}\{\mu(DLDD)+\mu(LLDD)\} - \beta_{3}\mu(LLD)\nonumber\\& - \beta_{2}\mu(DLD) - \beta_{1}\mu(DWLD) - \gamma_{3}\mu(WWLDD) - p(1-p)^{6}C_{LLWD} - p(1-p)^{6}C_{LLDW} \nonumber\\&- p^{2}C_{WDD} - p^{2}(3-3p+p^{2})(1-p)^{2}C_{LWD} - C_{3} - \beta_{2}C_{LWLD}\nonumber\\
={}& w_{4}(\mu) + p(2-16p+20p^{2}+7p^{3}-42p^{4}+51p^{5}-35p^{6}+7p^{7}+13p^{8}-14p^{9}+6p^{10}-p^{11})\nonumber\\&\mu(LD) - p^{2}\mu(DDD) - \gamma_{4}\mu(LDL)  - \gamma_{2}\mu(LDW) - \alpha_{3}\{\mu(DLDD)+\mu(LLDD)\} - \beta_{3}\mu(LLD) \nonumber\\&- \beta_{2}\mu(DLD) - \beta_{1}\mu(DWLD) - \gamma_{3}\mu(WWLDD) - p(1-p)^{6}C_{LLWD} - p(1-p)^{6}C_{LLDW} \nonumber\\&- p^{2}C_{WDD} - p^{2}(3-3p+p^{2})(1-p)^{2}C_{LWD} - C_{3} - \beta_{2}C_{LWLD},\label{wt_ineq_4_explained}
\end{align}

* the polynomial $\gamma_{4}=1-3p-2p^{2}+12p^{3}-31p^{4}+81p^{5}-156p^{6}+197p^{7}-168p^{8}+98p^{9}-38p^{10}+9p^{11}-p^{12}$ is strictly positive for all $p \in [0,0.345094)$,

* and the polynomial $\gamma_{3} = p^{3}(1-p)^{6}(1-3p+p^{3}-2p^{4}+2p^{6}-p^{7})$ is strictly positive for all $p \in (0,0.338338)$.

We now have our weight function inequality for $0.157175 < p \leqslant 0.201382$, since the coefficient of each term in the right side of (<ref>), apart from $w_{4}(\mu)$, is strictly negative for $p \in (0.157175,0.201382]$, thereby allowing (<ref>) to satisfy (<ref>). Note that (<ref>) reduces to the inequality in (<ref>) if we remove, apart from $w_{4}(\mu)$, $- p^{2}\mu(DDD)$ and $p(2-16p+20p^{2}+7p^{3}-42p^{4}+51p^{5}-35p^{6}+7p^{7}+13p^{8}-14p^{9}+6p^{10}-p^{11})\mu(LD)$, all other terms from the right side of (<ref>).

§.§ Construction of the weight function and proof of Theorem <ref> for the regime in (<ref>)

We now demonstrate the step-by-step construction of our weight function for the regime given in (<ref>), i.e. for all $(p,q)$ that satisfy the constraints $p = q > 0.10883$. The approach is very similar to the general idea outlined in <ref>, and the steps, while differing from those presented in <ref> in their details, follow a similar line of reasoning. As stated in <ref>, we begin by setting $\mathcal{C}_{1}=(D)_{0}$ and $c_{1}=1$ in (<ref>), which requires us to compute $\F_{p,p}\mu(D)$:

\begin{align}
\F_{p,p}\mu(D) ={}& (1-p)(1-2p)\{\mu(WD)+\mu(DW)\} + (1-2p)\mu(DD) + p(1-2p)\{\mu(LD)+\mu(DL)\}\nonumber\\
={}& 2(1-p)(1-2p)\mu(WD)+(1-2p)\mu(DD)+2p(1-2p)\mu(LD).\label{F_{p,p}mu(D)}
\end{align}

Note that our choice of setting $\mathcal{C}_{1}=(D)_{0}$ implies that, in the left side of the final weight function inequality, which must be of the form given in (<ref>), the terms of $\F_{p,p}\mu(D)$ appear, and these need to be bounded above by the terms in the right side of the final weight function inequality. Note that, when $p$ is small, the expression in (<ref>) becomes approximately the same as $2\mu(WD) + \mu(DD)$, which can be bounded above by $\mu(WD) + \mu(D)$. This, therefore, prompts us to set $\mathcal{C}_{2}=(W,D)_{0,1}$ and $c_{2}=1$. Consequently, there is need for the computation of $\F_{p,p}\mu(WD)$. Similar to the computation carried out in (<ref>), we use (<ref>) through (<ref>) to obtain

\begin{align}
\F_{p, p}\mu(WD) ={}& (2p - p^2) (1-p) (1-2p) \mu(WWD) + (1-p+p^2)p(1-2p) \mu(WLD) \nonumber\\& + (1-p+p^2)(1-p)(1-2p) \mu(LWD) + (1-p^2)p(1-2p) \mu(LLD) \nonumber\\&+ (2p-p^2)(1-2p) \mu(WDD) + (2p-p^2)(1-p)(1-2p) \mu(DWD) \nonumber\\&+ (2p-p^2)(1-2p) \mu(DDD) + (1-p+p^2)(1-2p) \mu(LDD) \nonumber\\& + (1-p+p^2)p(1-2p) \mu(DLD) + (2p-p^2)(1-p)(1-2p) \mu(WDW) \nonumber\\&+ (2p-p^2)p(1-2p) \mu(WDL) + (1-p+p^2)(1-p)(1-2p) \mu(LDW) \nonumber\\& + (1-p+p^2)p(1-2p) \mu(LDL) + (2p-p^2)(1-p)(1-2p) \mu(DDW) \nonumber\\& + (2p-p^2)p(1-2p) \mu(DDL).\label{F_{p,p}mu(WD)}
\end{align}

Note that the `leading terms' in the right side of (<ref>), when $p$ is small, are those involving $\mu(LWD)$, $\mu(LDD)$ and $\mu(LDW)$. Since we have chosen $\mathcal{C}_{1}=(D)_{0}$, $\mathcal{C}_{2}=(W,D)_{0,1}$ and $c_{1}=c_{2}=1$, the left side of (<ref>) contains $\F_{p,p}\mu(D)+\F_{p,p}\mu(WD)$, and when $p$ is small, this equals, approximately,

\begin{align}
{}&2\mu(WD) + \mu(DD) + \mu(LDD) + \mu(LDW) + \mu(LWD) \nonumber\\
={}& \{\mu(WD) + \mu(DD) + \mu(LDD) + \mu(LDW)\} + \mu(WD) + \mu(LWD),\nonumber
\end{align}

which can be bounded above by $\mu(D) + \mu(WD) + \mu(LWD)$.

Starting with our initial guess for our weight function, namely $w_0(\mu) = \mu(D) + \mu(WD)$, we obtain, using (<ref>) and (<ref>), the following weight function inequality:

\begin{align}
w_0(\F_{p, p}\mu)={}& w_0(\mu) \underbrace{- \mu(D)  + \F_{p, p}\mu(D)}_{\text{use \eqref{F_{p,p}mu(D)} and simplify}} - \mu(WD) + \F_{p, p}\mu(WD) \nonumber\\
={}& w_0(\mu) - (3p - 2p^2) \mu(DW) - 2p \mu(DD) - (1-p+2p^2) \mu(DL) + (1-p)(1-2p) \mu(WD) \nonumber\\
& + p(1-2p) \mu(LD) - \mu(WD)  \underbrace{+ \F_{p, p}\mu(WD)}_{\text{substitute using \eqref{F_{p,p}mu(WD)}}} \nonumber\\
&= w_0(\mu) \underbrace{- (3p - 2p^2) \mu(DW)}_{\text{substitute } \mu(DW) = \mu(WD)} - 2p \mu(DD) \underbrace{- (1-p + 2p^2) \mu(DL)}_{\text{(i)}} \underbrace{+ (1-p)(1-2p) \mu(WD)}_{\text{(ii)}} \nonumber \\
& \underbrace{+ p(1-2p) \mu(LD)}_{\text{(i)}} \underbrace{- \mu(WD)}_{\text{(ii)}} + (2p - p^2) (1-p) (1-2p) \mu(WWD) \nonumber\\
&  + (1-p+p^2)p(1-2p) \mu(WLD) + (1-p+p^2)(1-p)(1-2p) \mu(LWD)\nonumber \\
&  + (1-p^2)p(1-2p) \mu(LLD) + (2p-p^2)(1-2p) \mu(WDD) + (2p-p^2)(1-p)(1-2p) \mu(DWD) \nonumber\\
&  + (2p-p^2)(1-2p) \mu(DDD) + (1-p+p^2)(1-2p) \mu(LDD) + (1-p+p^2)p(1-2p) \mu(DLD) \nonumber\\
& + (2p-p^2)(1-p)(1-2p) \mu(WDW) + (2p-p^2)p(1-2p) \mu(WDL) \nonumber\\
& + (1-p+p^2)(1-p)(1-2p) \mu(LDW) + (1-p+p^2)p(1-2p) \mu(LDL) \nonumber\\
& + (2p-p^2)(1-p)(1-2p) \mu(DDW) + (2p-p^2)p(1-2p) \mu(DDL)\nonumber \\
={}& w_0(\mu)  \underbrace{- (3p - 2p^2) \mu(WD)} - 2p \mu(DD) \underbrace{- (1-2p + 4p^2) \mu(LD)}_{\text{combining terms labelled (i)}}   \underbrace{- (3p-2p^2) \mu(WD)}_{\text{combining terms labelled (ii)}} \nonumber\\
& + (2p - p^2) (1-p) (1-2p) \mu(WWD) + (1-p+p^2)p(1-2p) \mu(WLD) \nonumber\\
& + (1-p+p^2)(1-p)(1-2p) \mu(LWD) + (1-p^2)p(1-2p) \mu(LLD) \nonumber\\
& + (2p-p^2)(1-2p) \mu(WDD) + (2p-p^2)(1-p)(1-2p) \mu(DWD)\nonumber \\
& + (2p-p^2)(1-2p) \mu(DDD) + (1-p+p^2)(1-2p) \mu(LDD)  + (1-p+p^2)p(1-2p) \mu(DLD) \nonumber\\
& + (2p-p^2)(1-p)(1-2p) \mu(WDW) + (2p-p^2)p(1-2p) \mu(WDL)\nonumber \\
& + (1-p+p^2)(1-p)(1-2p) \mu(LDW) + (1-p+p^2)p(1-2p) \mu(LDL) \nonumber\\
& + (2p-p^2)(1-p)(1-2p) \mu(DDW) + (2p-p^2)p(1-2p) \mu(DDL)\nonumber \\
={}& w_0(\mu) \underbrace{- (2p-p^2)(1-2p) \mu(WD)}_{\text{expand using }\mu(WD) = \mu(WDW) + \mu(WDL) + \mu(WDD)\text{ }} \underbrace{- 2p \mu(DD)}_{\text{ expand using }\mu(DD) = \mu(DDW) + \mu(DDL) + \mu(DDD)} \nonumber \\
&\underbrace{- (1-p+p^2)(1-2p) \mu(LD)}_{\text{expand using }\mu(LD) = \mu(LDW) + \mu(LDL) + \mu(LDD)}  \underbrace{- ((1-2p +4p^2) - (1-p+p^2)(1-2p)) \mu(LD)}_{\text{expand using }\mu(LD) = \mu(WLD) + \mu(LLD) + \mu(DLD)} \nonumber\\
&\underbrace{- (6p-4p^2-(2p-p^2)(1-2p)) \mu(WD)}_{\text{expand using }\mu(WD) = \mu(WWD) + \mu(LWD) + \mu(DWD)} + (2p - p^2) (1-p) (1-2p) \mu(WWD) \nonumber\\
&+ (1-p+p^2)p(1-2p) \mu(WLD)  + (1-p+p^2)(1-p)(1-2p) \mu(LWD) \nonumber\\
&+ (1-p^2)p(1-2p) \mu(LLD) + (2p-p^2)(1-2p) \mu(WDD) \nonumber\\
&+ (2p-p^2)(1-p)(1-2p) \mu(DWD) + (2p-p^2)(1-2p) \mu(DDD) \nonumber\\
&+ (1-p+p^2)(1-2p) \mu(LDD) + (1-p+p^2)p(1-2p) \mu(DLD) \nonumber\\
& + (2p-p^2)(1-p)(1-2p) \mu(WDW) + (2p-p^2)p(1-2p) \mu(WDL)\nonumber \\
& + (1-p+p^2)(1-p)(1-2p) \mu(LDW) + (1-p+p^2)p(1-2p) \mu(LDL) \nonumber\\
& + (2p-p^2)(1-p)(1-2p) \mu(DDW) + (2p-p^2)p(1-2p) \mu(DDL)\nonumber\\
={}& w_0(\mu) \underbrace{- (2p-p^2)(1-2p) (\mu(WDW) + \mu(WDL) + \mu(WDD))} \nonumber\\
& \underbrace{-  2p (\mu(DDW) + \mu(DDL) + \mu(DDD))} \underbrace{- (1-p+p^2)(1-2p) (\mu(LDW) + \mu(LDL) + \mu(LDD))} \nonumber\\
& \underbrace{- ((1-2p +4p^2) - (1-p+p^2)(1-2p)) (\mu(WLD) + \mu(LLD) + \mu(DLD))}\nonumber \\
& \underbrace{- (6p-4p^2-(2p-p^2)(1-2p)) (\mu(WWD) + \mu(LWD) + \mu(DWD))} \nonumber\\
& + (2p - p^2) (1-p) (1-2p) \mu(WWD) + (1-p+p^2)p(1-2p) \mu(WLD) \nonumber\\
& + (1-p+p^2)(1-p)(1-2p) \mu(LWD) + (1-p^2)p(1-2p) \mu(LLD) \nonumber\\
& + (2p-p^2)(1-2p) \mu(WDD) + (2p-p^2)(1-p)(1-2p) \mu(DWD) + (2p-p^2)(1-2p) \mu(DDD)\nonumber \\
& + (1-p+p^2)(1-2p) \mu(LDD) + (1-p+p^2)p(1-2p) \mu(DLD)\nonumber \\
& + (2p-p^2)(1-p)(1-2p) \mu(WDW) + (2p-p^2)p(1-2p) \mu(WDL) \nonumber\\
& + (1-p+p^2)(1-p)(1-2p) \mu(LDW) + (1-p+p^2)p(1-2p) \mu(LDL)\nonumber \\
& + (2p-p^2)(1-p)(1-2p) \mu(DDW) + (2p-p^2)p(1-2p) \mu(DDL)\label{Fpp_inital_1}\\
={}&w_0(\mu) - (2p^2-5p^3+2p^4) \mu(WDW) \underbrace{- (2p - 7p^2 + 7p^3 - 2p^4) \mu(WDL)} \nonumber \\
& - (7p^2 - 7p^3 +2p^4) \mu(DDW) - (2p-2p^2+5p^3-2p^4) \mu(DDL) - (5p^2 - 2p^3) \mu(DDD) \nonumber\\
& \underbrace{- (p - 3p^2 + 3p^3 - 2p^4) \mu(LDW)}_{\text{substituting }\mu(LDW) = \mu(WDL)} - (1 - 4p + 6p^2 - 5p^3 + 2p^4) \mu(LDL) \nonumber\\
& - (4p^2 - p^3 + 2p^4) \mu(WLD) - (3p^2 + 3p^3 -2p^4)\mu(LLD) - (4p^2 - p^3 + 2p^4)\mu(DLD) \nonumber\\
& - (2p + 8p^2 - 9p^3 + 2p^4) \mu(WWD) - (-1 + 8p - 5p^2 + 3p^3 - 2p^4) \mu(LWD) \nonumber\\
& - (2p + 8p^2 - 9p^3 + 2p^4) \mu(DWD)\label{Fpp_initial_2}\\
={}& w_0(\mu) - (2p^2-5p^3+2p^4) \mu(WDW) \underbrace{- (3p - 10p^2 + 10p^3 - 4p^4) \mu(WDL)}_{\text{combining the highlighted terms}} \nonumber \\
& - (7p^2 - 7p^3 +2p^4) \mu(DDW) - (2p-2p^2+5p^3-2p^4) \mu(DDL) - (5p^2 - 2p^3) \mu(DDD) \nonumber\\
& - (1 - 4p + 6p^2 - 5p^3 + 2p^4) \mu(LDL) - (4p^2 - p^3 + 2p^4) \mu(WLD) - (3p^2 + 3p^3 -2p^4)\mu(LLD)\nonumber \\
& - (4p^2 - p^3 + 2p^4)\mu(DLD) - (2p + 8p^2 - 9p^3 + 2p^4) \mu(WWD) \nonumber\\
& - (-1 + 8p - 5p^2 + 3p^3 - 2p^4) \mu(LWD) - (2p + 8p^2 - 9p^3 + 2p^4) \mu(DWD).\label{wt_fn_ineq_1_regime_2}
\end{align}

We note here that we obtain (<ref>) from (<ref>) by combining together terms corresponding to every cylinder set. The only problematic term in the above expression is $-(-1 + 8p - 5p^2 + 3p^3 - 2p^4) \mu(LWD)$, since the coefficient of this term is strictly positive for sufficiently small values of $p$. To tackle this term, we make use of some of the existing negative terms in the right side of (<ref>), using the idea outlined in <ref>. We now update our weight function as follows:

\begin{align}
w_1(\mu) ={}& w_0(\mu) - (2p^2 - 5p^3 + 2p^4) \mu(WDW) - (3p - 10p^2 + 10p^3 - 4p^4) \mu(WDL) \nonumber\\&- (7p^2 - 7p^3 + 2p^4) \mu(DDW) - (2p - 2p^2 + 5p^3 - 2p^4) \mu(DDL) \nonumber\\&- (1 - 4p + 6p^2 - 5p^3 + 2p^4) \mu(LDL) - (4p^2 - p^3 + 2p^4) \mu(WLD) - (3p^2 + 3p^3 -2p^4) \mu(LLD) \nonumber\\&- (2p + 8p^2 - 9p^3 + 2p^4) \mu(WWD), \label{adjust_1_p=q}
\end{align}

which is exactly what we stated in (<ref>).

In order to incorporate this adjustment into our current weight function inequality, following the idea used in the deduction of (<ref>), we need to compute the expressions for $\F_{p, p}\mu(WDW)$, $\F_{p, p}\mu(WDL)$, $\F_{p, p}\mu(DDW)$, $\F_{p, p}\mu(DDL)$, $\F_{p, p}\mu(LDL)$, $\F_{p, p}\mu(WLD)$, $\F_{p, p}\mu(LLD)$ and $\F_{p, p}\mu(WWD)$. However, we need only partially compute these terms, since we only care about using these to negate, as much as possible, $-(-1 + 8p - 5p^2 + 3p^3 - 2p^4) \mu(LWD)$. Consequently, we actually obtain lower bounds for the above-mentioned terms.

We begin with $\F_{p, p}\mu(WDW)$, for which we need to compute the probability of the event $\{\F_{p, p}\eta(0) = W, \F_{p, p}\eta(1) = D, \F_{p, p}\eta(2) = W\}$. We focus on the configurations which satisfy $(\eta(1), \eta(2), \eta(3)) = (D, W, L)$. In this case, the event $\{(\F_{p, p}\eta(1), \F_{p, p}\eta(2)) = (D, W)\}$ occurs with probability $(1-p+p^2)(1-p)(1-2p)$. Note that

* when $\eta(0) = W$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $2p-p^2$.

* when $\eta(0) = L$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $1-p+p^2$.

* when $\eta(0) = D$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $2p-p^2$.

Using these observations, we obtain (again, recall that what follows is an inequality since we have ignored contributions from tuples $(\eta(0),\eta(1),\eta(2),\eta(3))$ that do not satisfy $(\eta(1), \eta(2), \eta(3)) = (D, W, L)$)

\begin{align}
\F_{p, p}\mu(WDW) \geqslant{}& (1-p+p^2)(1-p)(1-2p)\{(2p-p^2) \mu(WDWL) + (1-p+p^2)\mu(LDWL) \nonumber\\&+ (2p-p^2) \mu(DDWL)\}
%  ={}& (1-p+p^2)(1-p)(1-2p)(2p-p^2) \mu(DWL) \nonumber\\&+ (1-p+p^2)(1-p)(1-2p)(1-p)(1-2p) \mu(LDWL)\nonumber\\
\geqslant (1-p+p^2)(1-p)(1-2p)(2p-p^2) \mu(LWD).   \label{Fpp_WDW}
\end{align}

For $\F_{p, p}\mu(WDL)$, we need to compute the probability of the event $\{(\F_{p, p}\eta(0), \F_{p, p}\eta(1), \F_{p, p}\eta(2)) = (W, D, L)\}$. We consider the configurations which satisfy $(\eta(1), \eta(2), \eta(3)) = (D, W, L)$, so that the event $\{((\F_{p,p}\eta(1), \F_{p, p}\eta(2)) = (D, L)\}$ happens with probability $(p-p^2)(1-p)(1-2p)$. Note that

* when $\eta(0) = W$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $2p-p^2$.

* when $\eta(0) = L$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $1-p+p^2$.

* when $\eta(0) = D$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $2p-p^2$.

These observations yield

\begin{align}
\F_{p, p}\mu(WDL) \geqslant&{}  (1-p)(1-2p)(p-p^2)\{(2p-p^2) \mu(WDWL) + (1-p+p^2) \mu(LDWL) \nonumber\\&+ (2p-p^2) \mu(DDWL)\}
%    &= (1-p)(1-2p)(p-p^2)(2p-p^2) \mu(DWL) + (1-p)(1-2p)(p-p^2)(1-p)(1-2p) \mu(LDWL)\\
\geqslant (1-p)(1-2p)(p-p^2)(2p-p^2) \mu(LWD). \label{Fpp_WDL}
\end{align}

For $\F_{p, p}\mu(DDW)$, we need to compute the probability of the event $\{\F_{p, p}\eta(0) = D, \F_{p, p}\eta(1) = D, \F_{p, p}\eta(2) = W\}$. We focus on configurations which satisfy $(\eta(1), \eta(2), \eta(3)) = (D, W, L)$, so that the event $\{(\F_{p, p}\eta(1), \F_{p, p}\eta(2)) = (D, W)\}$ occurs with probability $(1-p+p^2)(1-p)(1-2p)$. Note that

* when $\eta(0) = W$, the event $\{\F_{p, p}\eta(0) = D\}$ occurs with probability $(1-p)(1-2p)$.

* when $\eta(0) = L$, the event $\{\F_{p, p}\eta(0) = D\}$ occurs with probability $p-2p^2$.

* when $\eta(0) = D$, the event $\{\F_{p, p}\eta(0) = D\}$ occurs with probability $1-2p$.

Using these observations, we obtain

\begin{align}
\F_{p, p}\mu(DDW)  \geqslant{}& (1-p+p^2)(1-p)(1-2p)\{(1-p)(1-2p) \mu(WDWL) + (p-2p^2) \mu(LDWL) \nonumber\\& + (1-2p) \mu(DDWL)\}
%&= (1-p+p^2)(1-p)(1-2p)(p-2p^2) \mu(DWL) + (1-p+p^2)(1-p)(1-2p)(1-2p)^2 \mu(WDWL) \\
%&\enspace+ (1-p+p^2)(1-p)(1-2p)(1-2p)(1-p) \mu(DDWL)\\
\geqslant (1-p+p^2)(1-p)(1-2p)(p-2p^2) \mu(LWD).  \label{Fpp_DDW}
\end{align}

For $\F_{p, p}\mu(DDL)$, we need to compute the probability of the event $\{\F_{p, p}\eta(0) = D, \F_{p, p}\eta(1) = D, \F_{p, p}\eta(2) = L\}$. We focus on configurations which satisfy $(\eta(1), \eta(2), \eta(3)) = (D, W, L)$, so that the event $\{(\F_{p, p}\eta(1), \F_{p, p}\eta(2)) = (D, L)\}$ occurs with probability $(p-p^2)(1-p)(1-2p)$. Note that

* when $\eta(0) = W$, the event $\{\F_{p, p}\eta(0) = D\}$ occurs with probability $(1-p)(1-2p)$.

* when $\eta(0) = L$, the event $\{\F_{p, p}\eta(0) = D\}$ occurs with probability $p-2p^2$.

* when $\eta(0) = D$, the event $\{\F_{p, p}\eta(0) = D\}$ occurs with probability $1-2p$.

Using these observations, we obtain

\begin{align}
\F_{p, p}\mu(DDL)  \geqslant{}& (p-p^2)(1-p)(1-2p)\{(1-p)(1-2p) \mu(WDWL) + (p-2p^2) \mu(LDWL) \nonumber\\&+ (1-2p) \mu(DDWL)\}
%&= (p-p^2)(1-p)(1-2p)(p-2p^2) \mu(DWL) + (p-p^2)(1-p)(1-2p)(1-2p)^2 \mu(WDWL) \\
%&\enspace+ (p-p^2)(1-p)(1-2p)(1-2p)(1-p) \mu(DDWL) \\
\geqslant (p-p^2)(1-p)(1-2p)(p-2p^2) \mu(LWD). \label{Fpp_DDL}
\end{align}

For $\F_{p, p}\mu(LDL)$, we need to compute the probability of the event $\{\F_{p, p}\eta(0) = L, \F_{p, p}\eta(1) = D, \F_{p, p}\eta(2) = L\}$. We focus on configurations which satisfy $(\eta(1), \eta(2), \eta(3)) = (D, W, L)$, so that the event $\{(\F_{p, p}\eta(1), \F_{p, p}\eta(2)) = (D, L)\}$ occurs with probability $(p-p^2)(1-p)(1-2p)$. Note that

* when $\eta(0) = W$, the event $\{\F_{p, p}\eta(0) = L\}$ occurs with probability $p-p^2$.

* when $\eta(0) = L$, the event $\{\F_{p, p}\eta(0) = L\}$ occurs with probability $p^2$.

* when $\eta(0) = D$, the event $\{\F_{p, p}\eta(0) = L\}$ occurs with probability $p^2$.

These observations yield

\begin{align}
\F_{p, p}\mu(LDL)  \geqslant{}& (p-p^2)(1-p)(1-2p)\{(p-p^2) \mu(WDWL) + p^2 \mu(LDWL) + p^2 \mu(DDWL)\} \nonumber \\
%&= (p-p^2)(1-p)(1-2p)p^2 \mu(DWL) + (p-p^2)(1-p)(1-2p)(p-2p^2) \mu(WDWL) \\
\geqslant{}& (p-p^2)(1-p)(1-2p)p^2 \mu(LWD). \label{Fpp_LDL}
\end{align}

For $\F_{p, p}\mu(WLD)$, we need to compute the probability of the event $\{\F_{p, p}\eta(0) = W, \F_{p, p}\eta(1) = L, \F_{p, p}\eta(2) = D\}$. We consider configurations which satisfy $(\eta(1), \eta(2), \eta(3)) = (L, W, D)$, so that the event $\{(\F_{p, p}\eta(1), \F_{p, p}\eta(2)) = (L, D)\}$ occurs with probability $(1-p)(1-2p)(p-p^2)$. Note that

* when $\eta(0) = W$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $1-p+p^2$.

* when $\eta(0) = L$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $1-p^2$.

* when $\eta(0) = D$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $1-p+p^2$.

Using these observations, we deduce

\begin{align}
\F_{p, p}\mu(WLD)  \geqslant{}& (1-p)(1-2p)(p-p^2)\{(1-p+p^2) \mu(WLWD) + (1-p^2) \mu(LLWD) \nonumber\\&+ (1-p+p^2) \mu(DLWD)\}
%&= (1-p)(1-2p)(p-p^2)(1-p+p^2) \mu(LWD) + (1-p)(1-2p)(1-p+p^2)(p-2p^2) \mu(LLWD) \\
\geqslant (1-p)(1-2p)(p-p^2)(1-p+p^2) \mu(LWD). \label{Fpp_WLD}
\end{align}

For $\F_{p, p}\mu(WWD)$, we need to compute the probability of the event $\{\F_{p, p}\eta(0) = W, \F_{p, p}\eta(1) = W, \F_{p, p}\eta(2) = D\}$. We focus on configurations which satisfy $(\eta(1), \eta(2), \eta(3)) = (L, W, D)$, so that the event $\{(\F_{p, p}\eta(1), \F_{p, p}\eta(2)) = (W, D)\}$ occurs with probability $(1-p)(1-2p)(1-p+p^2)$. Note that

* when $\eta(0) = W$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $1-p+p^2$.

* when $\eta(0) = L$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $1-p^2$.

* when $\eta(0) = D$, the event $\{\F_{p, p}\eta(0) = W\}$ occurs with probability $1-p+p^2$.

These observations yield

\begin{align}
\F_{p, p}\mu(WWD)  \geqslant{}& (1-p)(1-2p)(1-p+p^2)\{(1-p+p^2) \mu(WLWD) + (1-p^2) \mu(LLWD) \nonumber \\
&+ (1-p+p^2) \mu(DLWD)\}
%&= (1-p)(1-2p)(1-p+p^2)^2 \mu(LWD) + (1-p)(1-2p)(p-p^2)(p-2p^2) \mu(LLWD)  \\
\geqslant (1-p)(1-2p)(1-p+p^2)^2 \mu(LWD). \label{Fpp_WWD}
\end{align}

Finally, for $\F_{p, p}\mu(LLD)$, we need to compute the probability of the event $\{\F_{p, p}\eta(0) = L, \F_{p, p}\eta(1) = L, \F_{p, p}\eta(2) = D\}$. We focus on configurations which satisfy $(\eta(1), \eta(2), \eta(3)) = (L, W, D)$, so that the event $\{(\F_{p, p}\eta(1), \F_{p, p}\eta(2)) = (L, D)\}$ occurs with probability $(1-p)(1-2p)(p-p^2)$. Note that

* when $\eta(0) = W$, the event $\{\F_{p, p}\eta(0) = L\}$ occurs with probability $p-p^2$.

* when $\eta(0) = L$, the event $\{\F_{p, p}\eta(0) = L\}$ occurs with probability $p^2$.

* when $\eta(0) = D$, the event $\{\F_{p, p}\eta(0) = L\}$ occurs with probability $p^2$.

Using these observations, we obtain

\begin{align}
\F_{p, p}\mu(LLD) \geqslant{}& (1-p)(1-2p)(p-p^2)\{(p-p^2) \mu(WLWD) + p^2 \mu(LLWD) + p^2 \mu(DLWD)\} \nonumber\\
%&= (1-p)(1-2p)(p-p^2)p^2 \mu(LWD) + (1-p)(1-2p)(p-p^2)(p-2p^2) \mu(WLWD)  \\
\geqslant{}& (1-p)(1-2p)(p-p^2)p^2 \mu(LWD). \label{Fpp_LLD}
\end{align}

Incorporating the adjustment introduced in (<ref>) into the weight function inequality in (<ref>) via the idea demonstrated in (<ref>), and using the lower bounds obtained in (<ref>), (<ref>), (<ref>), (<ref>), (<ref>), (<ref>), (<ref>), (<ref>), we obtain

\begin{align}
w_1(\F_{p, p}\mu) =&{} w_1(\mu) \underbrace{+ (w_0(\F_{p, p}\mu) - w_0(\mu))}_{\text{substitute using \eqref{wt_fn_ineq_1_regime_2}}} - (2p^2 - 5p^3 + 2p^4) \F_{p, p}\mu(WDW) \nonumber \\
& - (3p - 10p^2 + 10p^3 - 4p^4) \F_{p, p}\mu(WDL) - (7p^2 - 7p^3 + 2p^4) \F_{p, p}\mu(DDW) \nonumber \\
& - (2p - 2p^2 + 5p^3 - 2p^4) \F_{p, p}\mu(DDL) - (1 - 4p + 6p^2 - 5p^3 + 2p^4) \F_{p, p}\mu(LDL) \nonumber \\
&- (4p^2 - p^3 + 2p^4) \F_{p, p}\mu(WLD)  - (3p^2 + 3p^3 -2p^4) \F_{p, p}\mu(LLD) \nonumber \\
&- (2p + 8p^2 - 9p^3 + 2p^4) \F_{p, p}\mu(WWD) + (2p^2 - 5p^3 + 2p^4) \mu(WDW) \nonumber \\
& + (3p - 10p^2 + 10p^3 - 4p^4) \mu(WDL) + (7p^2 - 7p^3 + 2p^4) \mu(DDW) \nonumber \\
&+ (2p - 2p^2 + 5p^3 - 2p^4) \mu(DDL) + (1 - 4p + 6p^2 - 5p^3 + 2p^4) \mu(LDL) \nonumber \\
& + (4p^2 - p^3 + 2p^4) \mu(WLD) + (3p^2 + 3p^3 -2p^4) \mu(LLD) \nonumber \\
&+ (2p + 8p^2 - 9p^3 + 2p^4) \mu(WWD) \nonumber \\
=&{} w_1(\mu) \underbrace{- (2p^2-5p^3+2p^4) \mu(WDW)}_\text{(i)} \underbrace{- (3p - 10p^2 + 10p^3 - 4p^4) \mu(WDL)}_\text{(ii)} \nonumber\\
& \underbrace{- (7p^2 - 7p^3 +2p^4) \mu(DDW)}_{\text{(iii)}} \underbrace{- (2p-2p^2+5p^3-2p^4) \mu(DDL)}_{\text{(iv)}} \nonumber \\
& - (5p^2 - 2p^3) \mu(DDD) \underbrace{- (1 - 4p + 6p^2 - 5p^3 + 2p^4) \mu(LDL)}_\text{(v)}  \nonumber\\
&\underbrace{- (4p^2 - p^3 + 2p^4) \mu(WLD)}_{\text{(vi)}} \underbrace{- (3p^2 + 3p^3 -2p^4)\mu(LLD)}_{\text{(vii)}} \nonumber\\
& - (4p^2 - p^3 + 2p^4)\mu(DLD) \underbrace{- (2p + 8p^2 - 9p^3 + 2p^4) \mu(WWD)}_{\text{(viii)}} \nonumber \\
&  - (-1 + 8p - 5p^2 + 3p^3 - 2p^4) \mu(LWD) - (2p + 8p^2 - 9p^3 + 2p^4) \mu(DWD) \nonumber \\
& - (2p^2 - 5p^3 + 2p^4) \F_{p, p}\mu(WDW) - (3p - 10p^2 + 10p^3 - 4p^4) \F_{p, p}\mu(WDL) \nonumber \\
& - (7p^2 - 7p^3 + 2p^4) \F_{p, p}\mu(DDW) - (2p - 2p^2 + 5p^3 - 2p^4) \F_{p, p}\mu(DDL) \nonumber \\
& - (1 - 4p + 6p^2 - 5p^3 + 2p^4) \F_{p, p}\mu(LDL) - (4p^2 - p^3 + 2p^4) \F_{p, p}\mu(WLD) \nonumber \\
& - (3p^2 + 3p^3 -2p^4) \F_{p, p}\mu(LLD) - (2p + 8p^2 - 9p^3 + 2p^4) \F_{p, p}\mu(WWD) \nonumber\\
& \underbrace{+ (2p^2 - 5p^3 + 2p^4) \mu(WDW)}_{\text{(i)}} \underbrace{+ (3p - 10p^2 + 10p^3 - 4p^4) \mu(WDL)}_{\text{(ii)}} \nonumber \\
&\underbrace{+ (7p^2 - 7p^3 + 2p^4) \mu(DDW)}_{\text{(iii)}} \underbrace{+ (2p - 2p^2 + 5p^3 - 2p^4) \mu(DDL)}_{\text{(iv)}} \nonumber \\
& \underbrace{+ (1 - 4p + 6p^2 - 5p^3 + 2p^4) \mu(LDL)}_\text{(v)} \underbrace{+ (4p^2 - p^3 + 2p^4) \mu(WLD)}_{\text{(vi)}} \nonumber \\
& \underbrace{+ (3p^2 + 3p^3 -2p^4) \mu(LLD)}_{\text{(vii)}} \underbrace{+ (2p + 8p^2 - 9p^3 + 2p^4) \mu(WWD)}_{\text{(viii)}} \nonumber \\
=&{} w_1(\mu) - (5p^2 - 2p^3) \mu(DDD) - (4p^2 - p^3 + 2p^4)\mu(DLD) \nonumber \\
& - (-1 + 8p - 5p^2 + 3p^3 - 2p^4) \mu(LWD) - (2p + 8p^2 - 9p^3 + 2p^4) \mu(DWD) \nonumber \\
& \underbrace{- (2p^2 - 5p^3 + 2p^4) \F_{p, p}\mu(WDW)}_{\text{use \eqref{Fpp_WDW}}} \underbrace{- (3p - 10p^2 + 10p^3 - 4p^4) \F_{p, p}\mu(WDL)}_{\text{use \eqref{Fpp_WDL}}} \nonumber \\
& \underbrace{- (7p^2 - 7p^3 + 2p^4) \F_{p, p}\mu(DDW)}_{\text{use \eqref{Fpp_DDW}}} \underbrace{- (2p - 2p^2 + 5p^3 - 2p^4) \F_{p, p}\mu(DDL)}_{\text{use \eqref{Fpp_DDL}}} \nonumber \\
& \underbrace{- (1 - 4p + 6p^2 - 5p^3 + 2p^4) \F_{p, p}\mu(LDL)}_{\text{use \eqref{Fpp_LDL}}} \underbrace{- (4p^2 - p^3 + 2p^4) \F_{p, p}\mu(WLD)}_{\text{use \eqref{Fpp_WLD}}}  \nonumber\\
& \underbrace{- (3p^2 + 3p^3 -2p^4) \F_{p, p}\mu(LLD)}_{\text{use \eqref{Fpp_LLD}}} \underbrace{- (2p + 8p^2 - 9p^3 + 2p^4) \F_{p, p}\mu(WWD)}_{\text{use \eqref{Fpp_WWD}}} \nonumber \\
\leqslant&{} w_1(\mu) - (5p^2 - 2p^3) \mu(DDD) - (4p^2 - p^3 + 2p^4)\mu(DLD) \nonumber \\
& \underbrace{- (-1 + 8p - 5p^2 + 3p^3 - 2p^4) \mu(LWD)} - (2p + 8p^2 - 9p^3 + 2p^4) \mu(DWD) \nonumber \\
&\underbrace{- (2p^2 - 5p^3 + 2p^4) ((1-p+p^2)(1-p)(1-2p)(2p-p^2) \mu(LWD))} \nonumber \\
&\underbrace{- (3p - 10p^2 + 10p^3 - 4p^4) ((1-p)(1-2p)(p-p^2)(2p-p^2) \mu(LWD))} \nonumber \\
& \underbrace{- (7p^2 - 7p^3 + 2p^4) ((1-p+p^2)(1-p)(1-2p)(p-2p^2) \mu(LWD))} \nonumber \\
& \underbrace{- (2p - 2p^2 + 5p^3 - 2p^4) ((p-p^2)(1-p)(1-2p)(p-2p^2) \mu(LWD))} \nonumber \\
& \underbrace{- (1 - 4p + 6p^2 - 5p^3 + 2p^4) ((p-p^2)(1-p)(1-2p)p^2 \mu(LWD))} \nonumber \\
& \underbrace{- (4p^2 - p^3 + 2p^4) ((1-p)(1-2p)(p-p^2)(1-p+p^2) \mu(LWD))} \nonumber \\
& \underbrace{- (3p^2 + 3p^3 -2p^4) ((1-p)(1-2p)(p-p^2)p^2 \mu(LWD))} \nonumber \\
& \underbrace{- (2p + 8p^2 - 9p^3 + 2p^4) ((1-p)(1-2p)(1-p+p^2)^2 \mu(LWD))} \nonumber \\
=&{} w_1(\mu) - (5p^2 - 2p^3) \mu(DDD) - (4p^2 - p^3 + 2p^4)\mu(DLD) - (2p + 8p^2 - 9p^3 + 2p^4) \mu(DWD) \nonumber \\
& \underbrace{+ (1 - 10p + 7p^2 + 64p^4 - 292p^5 + 583p^6 - 663p^7 + 447p^8 - 168p^9 + 28p^{10}) \mu(LWD)}_{\text{obtained by combining the terms highlighted above}} \nonumber \\
\leqslant &{} w_1(\mu) + (1 - 10p + 7p^2 + 64p^4 - 292p^5 + 583p^6 - 663p^7 + 447p^8 - 168p^9 + 28p^{10}) \mu(LWD),\nonumber
\end{align}

which is exactly what we stated in (<ref>). This brings us to the conclusion of the construction of our weight function for $(p,q)$ belonging to (<ref>).

[Bala and Goyal, 1998]
Venkatesh Bala and Sanjeev Goyal.
Learning from neighbours.
The review of economic studies, 650 (3):0
595–621, 1998.

[Bala and Goyal, 2000]
Venkatesh Bala and Sanjeev Goyal.
A noncooperative model of network formation.
Econometrica, 680 (5):0 1181–1229, 2000.

[Bhasin et al., 2022]
Dhruv Bhasin, Sayar Karmakar, Moumanti Podder, and Souvik Roy.
Ergodicity of a generalized probabilistic cellular automaton with
parity-based neighbourhoods.
arXiv preprint arXiv:2212.01753, 2022.

[Bhasin et al., 2023]
Dhruv Bhasin, Sayar Karmakar, Moumanti Podder, and Souvik Roy.
On a class of pca with size-3 neighborhood and their applications in
percolation games.
Electronic Journal of Probability, 28:0 1–60, 2023.

[Bollabás and Stacey, 1997]
Béla Bollabás and Alan Stacey.
Approximate upper bounds for the critical probability of oriented
percolation in two dimensions based on rapidly mixing markov chains.
Journal of Applied Probability, 340 (4):0
859–867, 1997.

[Borgne and Marckert, 2007]
Yvan Le Borgne and Jean-François Marckert.
Directed animals and gas models revisited.
the electronic journal of combinatorics, 140
(1):0 R71, 2007.

[Bresler et al., 2022]
Guy Bresler, Chenghao Guo, and Yury Polyanskiy.
Linear programs with polynomial coefficients and applications to 1d
cellular automata.
arXiv preprint arXiv:2204.06357, 2022.

[Broadbent and Hammersley, 1957]
Simon R Broadbent and John M Hammersley.
Percolation processes: I. crystals and mazes.
In Mathematical proceedings of the Cambridge philosophical
society, volume 53, pages 629–641. Cambridge University Press, 1957.

[Bušić et al., 2013]
Ana Bušić, Jean Mairesse, and Irene Marcovici.
Probabilistic cellular automata, invariant measures, and perfect
Advances in Applied Probability, 450 (4):0
960–980, 2013.

[Chatterjee and Xu, 2004]
Kalyan Chatterjee and Susan H Xu.
Technology diffusion by learning from neighbours.
Advances in Applied Probability, 360 (2):0
355–376, 2004.

[Day and Falgas-Ravry, 2021]
A Nicholas Day and Victor Falgas-Ravry.
Maker–breaker percolation games i: crossing grids.
Combinatorics, Probability and Computing, 300
(2):0 200–227, 2021a.

[Day and Falgas-Ravry, 2021]
A Nicholas Day and Victor Falgas-Ravry.
Maker-breaker percolation games ii: Escaping to infinity.
Journal of Combinatorial Theory, Series B, 151:0
482–508, 2021b.

[Dobrušin et al., 1990]
RL Dobrušin, VI Kriukov, and AL Toom.
Stochastic cellular systems: ergodicity, memory,
Manchester University Press, 1990.

[Durrett, 1984]
Richard Durrett.
Oriented percolation in two dimensions.
The Annals of Probability, 120 (4):0
999–1040, 1984.

[Durrett and Griffeath, 1983]
Richard Durrett and David Griffeath.
Supercritical contact processes on z.
The Annals of Probability, pages 1–15, 1983.

[Dvořák et al., 2021]
Vojtěch Dvořák, Adva Mond, and Victor Souza.
The maker-breaker percolation game on the square lattice.
arXiv preprint arXiv:2105.12864, 2021.

[Dvořák et al., 2024]
Vojtěch Dvořák, Adva Mond, and Victor Souza.
The maker-breaker percolation game on a random board.
arXiv preprint arXiv:2402.17547, 2024.

[Ellison and Fudenberg, 1993]
Glenn Ellison and Drew Fudenberg.
Rules of thumb for social learning.
Journal of political Economy, 1010 (4):0
612–643, 1993.

[Elsayed et al., 2017]
Wesam M Elsayed, Mohammed Elmogy, and B El-Desouky.
Evolutionary behavior of dna sequences analysis using non-uniform
probabilistic cellular automata model.
Cincia e Tcnica Vitivincola, 32:0 137–148, 2017.

[Griffeath, 1981]
David Griffeath.
The basic contact processes.
Stochastic Processes and their Applications, 110
(2):0 151–185, 1981.

[Hartarsky and Szabó, 2021]
I Hartarsky and R Szabó.
Generalised oriented site percolation, probabilistic cellular
automata and bootstrap percolation.
arXiv preprint arXiv, 2021.

[Hartarsky, 2022]
Ivailo Hartarsky.
Bootstrap percolation, probabilistic cellular automata and sharpness.
Journal of Statistical Physics, 1870 (3):0
1–17, 2022.

[Holroyd et al., 2019]
Alexander E Holroyd, Irène Marcovici, and James B Martin.
Percolation games, probabilistic cellular automata, and the hard-core
Probability Theory and Related Fields, 1740
(3):0 1187–1217, 2019.

[Karmakar et al., 2023]
Sayar Karmakar, Moumanti Podder, Souvik Roy, and Soumyarup Sadhukhan.
Phase transition in percolation games on rooted galton-watson trees.
arXiv preprint arXiv:2303.11402, 2023.

[Lebowitz et al., 1990]
Joel L Lebowitz, Christian Maes, and Eugene R Speer.
Statistical mechanics of probabilistic cellular automata.
Journal of statistical physics, 590 (1):0
117–170, 1990.

[Louis and Nardi, 2018]
Pierre-Yves Louis and Francesca R Nardi.
Probabilistic cellular automata.
Emergence, Complexity, Computation, 27, 2018.

[Mairesse and Marcovici, 2014]
Jean Mairesse and Irene Marcovici.
Around probabilistic cellular automata.
Theoretical Computer Science, 559:0 42–72, 2014.

[Popova et al., 2015]
E Popova, Y Staraselski, A Brahme, RK Mishra, and K Inal.
Coupled crystal plasticity–probabilistic cellular automata approach
to model dynamic recrystallization in magnesium alloys.
International Journal of Plasticity, 66:0 85–102,

[Propp and Wilson, 1996]
James Gary Propp and David Bruce Wilson.
Exact sampling with coupled markov chains and applications to
statistical mechanics.
Random Structures & Algorithms, 90 (1-2):0
223–252, 1996.

[Wallwork, 2022]
Freddie Wallwork.
Maker-breaker-crossing-game on the triangular grid-graph.
arXiv preprint arXiv:2201.01348, 2022.