# Dynamic GPU Energy Optimization for Machine Learning Training Workloads

Farui Wang, Weizhe Zhang, Shichao Lai, Meng Hao, and Zheng Wang  F. Wang, W.
Zhang, S. Lai, and M. Hao are with the School of Cyberspace Science at Harbin
Institute of Technology, Harbin 150000, China.
<EMAIL_ADDRESS>Z. Wang is with the School of Computing
at University of Leeds, United Kingdom.
E-mail<EMAIL_ADDRESS>
###### Abstract

GPUs are widely used to accelerate the training of machine learning workloads.
As modern machine learning models become increasingly larger, they require a
longer time to train, leading to higher GPU energy consumption. This paper
presents GPOEO, an online GPU energy optimization framework for machine
learning training workloads. GPOEO dynamically determines the optimal energy
configuration by employing novel techniques for online measurement, multi-
objective prediction modeling, and search optimization. To characterize the
target workload behavior, GPOEO utilizes GPU performance counters. To reduce
the performance counter profiling overhead, it uses an analytical model to
detect the training iteration change and only collects performance counter
data when an iteration shift is detected. GPOEO employs multi-objective models
based on gradient boosting and a local search algorithm to find a trade-off
between execution time and energy consumption. We evaluate the GPOEO by
applying it to 71 machine learning workloads from two AI benchmark suites
running on an NVIDIA RTX3080Ti GPU. Compared with the NVIDIA default
scheduling strategy, GPOEO delivers a mean energy saving of 16.2% with a
modest average execution time increase of 5.1%.

###### Index Terms:

Dynamic energy optimization, online application iteration detection, multi-
objective machine learning, GPU

##  1 Introduction

In recent years, deep neural networks (DNNs) have demonstrated breakthrough
effectiveness in various tasks that were once deemed impossible [1, 2].
Training an effective DNN requires performing expensive training on a large
number of samples. As the model training time increases, the energy
consumption of machine learning training workloads also grows. This is a
particular concern for high-performance GPUs because they are widely used to
train DNN workloads but are less energy-efficient than their CPU counterparts.
As a result, there is a critical need to reduce the energy consumption for
GPUs when training machine learning workloads. Achieving this goal can reduce
the maintenance cost and allow users to train larger models within the same
budget.

Most of the existing studies in general GPU energy optimization are offline
techniques [3, 4, 5, 6, 7]. These techniques require profiling applications
ahead of time [3, 4, 5, 7] or analyzing their source code [6] in advance to
collect application features. These approaches cannot adapt to the change of
the program behavior and can incur expensive profiling overhead. Other
approaches change the internal working mechanisms of machine learning (ML)
models [8, 9], but they are specific to the ML algorithms used and do not
generalize to other ML methods.

Recently, efforts have been made to target online GPU power optimization. The
work presented in [10] proposes a dynamic power management method for
integrated APUs. ODPP [11] is another online dynamic power-performance
management framework. ODPP detects the periods of applications to build
prediction models. However, their models can only detect coarse-grained phase
change patterns.

This work aims to provide a better dynamic GPU energy optimization method for
iterative ML training workloads. We present GPOEO, a micro-intrusive 111Micro-
intrusive means we require minor changes to the program source code. GPU
online energy optimization framework. GPOEO only requires the user to mark the
beginning and the end of the target code region. GPOEO can then automatically
collect the relevant information to monitor the program behavior to identify
the repeat workload patterns and adjust the energy optimization scheme
accordingly.

GPOEO trades execution time for energy efficiency. To this end, we employ
multi-objective optimization models built on the XGBoost Classifier [12]. As a
departure from existing online GPU power optimization schemes, GPOEO leverages
the fine-grained runtime information provided by the hardware performance
counters to model the system and program behavior to build more accurate
decision models. We use the predictive model as a cost function to search for
the optimal energy configuration for the current workload pattern. These
supporting methods enable us to develop a period detection algorithm based on
the fast Fourier transform (FFT) and feature sequence similarity evaluation to
identify if a changed training iteration takes place and adjust our
optimization accordingly.

We evaluate GPOEO by applying it to 71 machine learning workloads from three
AI benchmark suites [13]. We test our approach on an NVIDIA RTX3080Ti GPU.
Experimental results show that GPOEO can reduce GPU energy consumption by over
20% (16.2% on average), with most execution time increments less than 7% (5.1%
on average) when compared to the NVIDIA default GPU scheduling strategy.

This paper makes the following contributions:

  * •

It is the first work to exploit performance counter metrics to perform online
energy prediction and optimization for discrete GPUs. By minimizing the
instrument and measurement overhead, our approach improves the practicability
of online GPU profiling.

  * •

It presents a robust detection algorithm to automatically detect the iterative
period of ML applications from the GPU resource traces (Section 4.1).

  * •

It showcases how an effective GPU online energy optimization framework can be
constructed as a cost model to quickly identify a good energy configuration.

Online material: The GPOEO framework is publicly available at
https://github.com/ruixueqingyang/GPOEO.

##  2 Background and Motivation

###  2.1 GPU configuration and profiling tools

NVIDIA provides the NVML [14] and CUPTI [15] library for reconfiguring,
measuring, and profiling its GPUs. The NVML [14] can set Streaming
Multiprocessor (SM) clock frequency, global memory clock frequency (only
certain types of NVIDIA GPUs), and powercap online. It also supports measuring
power, SM utilization, and global memory utilization. The CUPTI [15] can
profile performance counter. These tools make GPU online energy optimization
possible. In this work, we adjust the clock frequency of the GPU SM and global
memory to achieve energy saving.

###  2.2 Motivation

####  2.2.1 Energy Optimization Potential

The training phase of machine learning usually uses high-performance GPUs as
accelerators. GPUs consume a lot of energy and time. To explore the energy-
saving potential on GPUs, we run five applications in AIBench [13] and
benchmarking-gnns [16] on all combinations of SM and memory clock frequencies
and select the best configurations for minimal energy consumption within the
slowdown constraint of 5%. Figure 1 shows the oracle results of energy saving,
slowdown, and ED2P ($Energy\times Dealy^{2}$) saving. The AI_FE, AI_S2T, and
SBM_GIN are relatively compute-intensive and save significant energy
(14.9%-22.4%). The CLB_MLP and TSP_GatedGCN are relatively memory-intensive
and save considerable energy (18.0%-26.4%). These results highlight that both
compute-intensive and memory-intensive ML training workloads have the chance
to save energy with acceptable slowdown.

####  2.2.2 Make Energy Optimization Practical

Most existing studies on GPU energy optimization are offline and need domain
knowledge and complex offline profiling. Thus, users or researchers can hardly
apply these studies in practice. An ideal online GPU energy optimization
system should be non-intrusive to applications and transparent to users.
Majumdar’s work [10] only applies to AMD APUs. Motivated by drawbacks, we
propose an online energy optimization framework called GPOEO. Users only need
to insert the Begin and End APIs, and the GPOEO automatically optimizes energy
online.

Figure 1: Oracle ED2P saving of ML applications

(a) MLC_3WLGNN application (b) SP_GCN application

Figure 2: Period detection errors of ODPP and GPOEO under different SM clock
frequencies

####  2.2.3 Reduce Period Detection Error

Online sampling time series of power and utilization can reflect the periodic
pattern. ODPP [11] uses the Fourier transform algorithm to detect periods,
namely the execution time of one major iteration. However, according to our
experimental results, the period error of ODPP [11] is quite large when the
periodicity is not apparent. To solve this shortcoming, we propose a robust
period detection algorithm. Figure 2 shows the absolute percentage errors of
period detection with ODPP and our algorithm GPOEO under different SM clock
frequencies on two ML applications. The “Default” means the NVIDIA default
scheduling strategy. The period detection errors of ODPP are pretty
significant and unstable, while the period detection errors of our GPOEO are
less than 5% under all SM clock frequencies.

####  2.2.4 Using GPU Performance Counters

ODPP [11] uses power, SM utilization, and memory utilization as features to
predict energy and execution time. However, these coarse-grained features are
inadequate to give accurate predictions for some machine learning
applications. We give an example in Figure 3. Applications in each pair have
similar average power and utilization under the same reference clock frequency
configuration, but their optimal SM clocks for ED2P are different (memory
frequency fixed at 9251MHz). In light of this observation, we wish to use more
fine-grained metrics to capture the subtle interactions between the
application and the hardware. To this end, we use hardware performance counter
metrics as features to build predictive models to estimate energy and
execution time. Later in the paper, we show that this strategy allows us to
build more accurate prediction models, which in turn lead to better
optimization decisions. The key challenges here are reducing the overhead of
performance counter profiling and minimizing code modifications.

Figure 3: ML applications with similar coarse-grained features and different
optimal SM clocks for ED2P

##  3 Overview of Our Approach

This section defines the scope of the work and gives an overview of our
approach.

###  3.1 Problem Formulation

This work aims to find an optimal SM and memory clock frequency configuration
to balance the GPU energy consumption and execution time for ML training
workloads. Our goal can be formulated as follows:

$\begin{split}\mathrm{min}\quad
F_{SM}&=f_{obj}\left(\widehat{eng_{SM}},\widehat{time_{SM}}\right)\\\
\mathrm{s.t.}\ \widehat{eng_{SM}}&=EngMdl_{SM}\left(\textbf{w}_{SM}\right),\\\
\widehat{time_{SM}}&=TimeMdl_{SM}\left(\textbf{w}_{SM}\right),\\\
\textbf{w}_{SM}&=\left\\{SMgear_{i},\textbf{Feature}\right\\},\\\
SMgear_{i}&\in\left\\{SMgear_{1},\dots,SMgear_{m}\right\\},\\\
\textbf{Feature}&=\left\\{feature_{1},\dots,feature_{q}\right\\}.\end{split}$
(1)

$\begin{split}\mathrm{min}\quad
F_{Mem}&=f_{obj}\left(\widehat{eng_{Mem}},\widehat{time_{Mem}}\right)\\\
\mathrm{s.t.}\
\widehat{eng_{Mem}}&=EngMdl_{Mem}\left(\textbf{w}_{Mem}\right),\\\
\widehat{time_{Mem}}&=TimeMdl_{Mem}\left(\textbf{w}_{Mem}\right),\\\
\textbf{w}_{Mem}&=\left\\{Memgear_{i},\textbf{Feature}\right\\},\\\
Memgear_{i}&\in\left\\{Memgear_{1},\dots,Memgear_{p}\right\\}.\end{split}$ (2)

Table I lists the variables used in our problem formulation. We note that our
approach can be applied to an arbitrary objective function. We select the
energy consumption with an execution time increase constraint as our objective
function to explicitly control the performance loss. Like [17], we assume that
the search space of SM and memory clocks is convex and optimize the SM
frequency and memory frequency in order. We use four prediction models to
estimate energy and time with different SM and memory clock frequencies. Then
we select the SM and memory clock configuration that can best satisfy the
optimization goal.

TABLE I: Description of Parameters Notation |  Description
---|---
$f_{obj}$ |  objective function
$\widehat{eng_{SM}}$ |  energy consumption predicted with the SM clock
$\widehat{time_{SM}}$ |  execution time predicted with the SM clock
$EngMdl_{SM}$ |  energy prediction model with the SM clock
$TimeMdl_{SM}$ |  time prediction model with the SM clock
$SMgear_{i}$ |  one SM gear represents an SM clock frequency
$\textbf{w}_{SM}$ |  the input vector containing SM clock
$\widehat{eng_{Mem}}$ |  energy consumption predicted with the memory clock
$\widehat{time_{Mem}}$ |  execution time predicted with the memory clock
$EngMdl_{Mem}$ |  energy prediction model with the memory clock
$TimeMdl_{Mem}$ |  time prediction model with the memory clock
$Memgear_{i}$ |  one memory gear represents a memory clock frequency
$\textbf{w}_{Mem}$ |  the input vector containing memory clock
Feature |  feature vector measured under the reference clock configuration from the ML applications
Figure 4: Overview of the GPOEO workflow.

###  3.2 Framework Overview

GPOEO includes two stages, shown in Figure 4. In the offline training stage,
we run representative benchmarks on each SM and memory clock frequencies ( 1)
to collect performance counter metrics on the reference SM and memory
frequencies and energy-time data on all frequencies. Then we train multi-
objective models ( 2). In the online optimization stage, we measure energy and
performance counter metrics in one detected period ( 3,  4), then predict the
optimal SM and memory frequencies ( 5,  6). After that, we try frequencies
around the predicted optimal configuration and compare the measured energy-
time data to search for the actual optimal configuration ( 7). Finally, we set
the actual optimal configuration and monitor energy characteristics ( 8). If
the fluctuation of energy characteristics exceeds the threshold, another
optimization process will start.

##  4 Design and Implement

###  4.1 Robust Period Detection

Iterative ML workloads exhibit periodic behavior across iterations. We treat
one period, namely one iteration, as basic unit for online metric measurement
and evaluation. Our approach does not rely on offline code instrumentation to
reduce developer involvement.

####  4.1.1 Fourier Transform: Get Candidate Periods

To detect the period change, we leverage the Fourier transform. This
established methodology is widely used in signal processing to detect the
dominant frequency and period. In our scenario, we assume the periodic feature
of ML applications, such as GPU power and utilization, can be expressed as a
time-domain function $\mathcal{F}(t)$. Generally speaking, $\mathcal{F}(t)$ is
periodic and can be expressed as a linear combination of trigonometric series
(know as Fourier Series) in exponential form as:

$\mathcal{F}\left(t\right)=\sum_{n=-\infty}^{\infty}C_{n}e^{{2\pi
jnt}/{T_{iter}}}$

where $C_{n}$ are Fourier coefficients.

We can get a series of frequency components via Fourier transform:

$\mathcal{F}(\omega)=2\pi\sum_{n=-\infty}^{\infty}C_{n}\delta\left(\omega-2\pi
n/T_{iter}\right)$

the frequency $\mathcal{F}(\omega)$ is a series of impulse functions (i.e.,
$\delta$) located at $2\pi n/T_{iter}$, with amplitude proportional to
$C_{n}$. These impulses represent different frequency components in
$\mathcal{F}(t)$. The one with the largest amplitude is the major frequency
component. The iterative period $T_{iter}$ of the ML application can be
calculated as $T_{iter}=1/f_{major}$, where $f_{major}$ is the frequency of
the major frequency component.

####  4.1.2 Feature Sequence Similarity: Find Accurate Periods

As mentioned in Section 2.2.3, the period detection results of the Fourier
transform may have vast errors. Our period calculation algorithm (Algorithm 1)
combines the fast Fourier transform (FFT) and feature sequence similarity
(Algorithm 2) to reduce these errors. We find amplitude peaks and
corresponding periods $TPeak$ in the result of FFT (line 1-3). Then we select
periods $Tpeak_{m}$ with relatively high peaks as candidate periods $Tcand$
(line 4-5). We set the peak coefficient $c_{peak}$ to 0.6-0.7 empirically.
Then we use feature sequence similarity (Algorithm 2) to evaluate and select
the best candidate period with minimal error. Finally, we perform a local
search around the best candidate period to further improve accuracy.

Algorithm 1 Period calculation algorithm based on FFT and feature sequence
similarity

Input: feature sampling sequence $\textbf{Smp}=\\{s_{1},\dots,s_{N}\\}$,
sampling interval $T_{s}$
Output: iterative period $T_{iter}$, error of period $err$

1:$Freq,Ampl=\\{freq_{i}\\},\\{ampl_{i}\\}=$FFT$(\textbf{Smp},T_{s})$

2:$T=\\{T_{i}\\}=\\{1/freq_{i}\\}$

3:Find peaks in $Ampl$, get the set of peaks $AmplPeak=\\{amplpeak_{m}\\}$ and
the set of corresponding periods $TPeak=\\{Tpeak_{m}\\}$

4:$IndexCand=\\{idxcand_{k}\\}$

5:$\qquad\qquad=\\{m|amplpeak_{m}>c_{peak}\times max(AmplPeak)\\}$

6:$TCand=\\{Tcand_{p}\\}=\\{Tpeak_{idxcand_{k}}\\}$

7:for $Tcand_{p}\in TCand$ do

8: $err_{p}=$ Algorithm2($Tcand_{p},\textbf{Smp},T_{s}$)

9:end for

10:Find $err_{idxmin}=min(\\{err_{p}\\})$

11:$Tcand_{opt}=Tcand_{idxmin}$

12:$N_{T}=T_{s}\times(N-1)/Tcand_{opt},$

13:$T_{low}=Tcand_{opt}\times(1-1/(N_{T}+1))$

14:$T_{up}=Tcand_{opt}\times(1+1/(N_{T}-1))$

15:Construct an arithmetic sequence $TLocal=\\{Tlocal_{q}\\},$

16:where $Tlocal_{q}=T_{low}+(q-1)\times T_{accu},$

17:$\qquad\quad q=1,\dots,(T_{up}-T_{up})/T_{accu}$

18:for $Tlocal_{q}\in TLocal$ do

19: $errlocal_{q}=$Algorithm2($Tlocal_{p},\textbf{Smp},T_{s}$)

20:end for

21:Find $err=err_{idxmin}=min(\\{errlocal_{q}\\})$

22:$T_{iter}=Tlocal_{idxmin}$

23:return $T_{iter},err$

We propose the feature sequence similarity algorithm (Algorithm 2) to evaluate
candidate periods. We divide the feature sampling curve into several sub-
curves, and the time duration of each sub-curve is equal to the candidate
period (line 1-4). The more similar the curves are, the closer the candidate
period is to the actual period. So we evaluate the similarity of each pair of
adjacent sub-curves (line 5-18).

Each sub-curve is a time series, and calculating the Euclidean distance
between corresponding points is a common method to measure the similarity of
time series. However, in our scenario, the Euclidean distance is susceptible
to high-frequency interference and reports the wrong similarity. Inspired by
this, instead of calculating the distance of each pair of corresponding
points, we group the sampling data within a series and evaluate the distance
between the corresponding groups. Specifically, we use the Gaussian mixture
model algorithm to cluster each sub-curves into N groups (line 8-11). Then,
for each group, we calculate the relative average amplitudes (line 12-13). The
average operation can eliminate the influence of high-frequency interference.
Later, we calculate the symmetric mean absolute percentage error (SMAPE) of
the current group pair (line 14). Finally, we calculate the weighted average
of all SMAPEs as similarity error (line 16-17). The weights are the numbers of
sampling points in groups. When all adjacent sub-curves are evaluated, we
treat the mean similarity error as the error of $T_{i}ter$ (line 19).

Algorithm 2 Feature sequence similarity algorithm

Input: Period to be evaluated $T_{iter}$, feature sampling sequence
$\textbf{Smp}=\\{s_{1},\dots,s_{N}\\}$, sampling interval $T_{s}$
Output: error of period $Err_{T}$

1:$Num_{T}=\lfloor s_{N}/T_{iter}\rfloor;Num_{s}=\lfloor T/T_{s}\rfloor$

2:for $i\in\\{1,\dots Num_{T}\\}$ do

3: $\textbf{Smp}_{i}=\\{s_{(i-1)\times Num_{s}+1},\dots,s_{i\times
Num_{s}}\\}=\\{ss_{i,j}\\}$

4: $(j=1,\dots,Num_{s})$

5:end for

6:for $i\in\\{1,\dots,Num_{T}-1\\}$ do

7: $Mean_{prev}=mean(\textbf{Smp}_{i})$

8: $Mean_{back}=mean(\textbf{Smp}_{i+1})$

9:
$\\{\textbf{GaGrp}_{1},\dots,\textbf{GaGrp}_{NumG}\\}=$Gauss$(\textbf{Smp}_{i},NumG)$

10: where $\textbf{GaGrp}_{j}=\\{idx_{j,1},\dots,idx_{j,Numj}\\}$

11: for $j\in\\{1,\dots,NumG\\}$ do

12: $\textbf{Grp}_{prev}=\\{ss_{i,idx_{j,1}},\dots,ss_{i,idx_{j,Numj}}\\}$

13: $\textbf{Grp}_{back}=\\{ss_{i+1,idx_{j,1}},\dots,ss_{i+1,idx_{j,Numj}}\\}$

14: $RelValPrev_{j}=mean(\textbf{Grp}_{prev})-Mean_{prev}$

15: $RelValBack_{j}=mean(\textbf{Grp}_{back})-Mean_{back}$

16: $grperr_{j}=$SMAPE$(RelValPrev_{j},RelValBack_{j})$

17: end for

18: $Weight=\\{|GaGrp_{1}|,\dots,|GaGrp_{NumG}|\\}$

19: $err_{i}=avg(\\{grperr_{1},\dots,grperr_{NumG}\\},Weight)$

20:end for

21:return $Err_{T}=mean(\\{err_{1},\dots,err_{Num_{T}-1}\\})$

_Note: Gauss = the Gaussian mixture model clustering algorithm_

####  4.1.3 Online Robust Period Detection Algorithm Framework

To get accurate $T_{iter}$ dynamically, we design an online robust period
detection algorithm framework (Algorithm 3). The framework calculates
$T_{iter}$ in a rolling form while sampling the power and utilization of the
GPU until the $T_{iter}$ is stable. First, we get the initial period
$T_{init}$, using Algorithm 2. If sampling duration is short than
$c_{measure}$ times $T_{init}$ ($c_{measure}$ is set to 2 empirically), it is
too short to do a rolling calculation, so we calculate the required sampling
duration, skip rolling calculation, and return (line2-6). If the sampling
duration is long enough, we get some updated samples by setting $t_{start}$
(line 7). Samples before $t_{start}$ are ignored because they may be outdated.
We set $step=0.5$ and $c_{eval}=6.5$ according to our experiments. Then, the
rolling period calculation begins. In each iteration, we calculate the period
(line 9-11) and increase $t_{start}$ to exclude more outdated samples for the
next iteration (line 12). With the rolling period calculation, we get a
sequence of periods with errors (line 14). If an ML application runs in the
regular iteration phase, these periods should be similar. If the difference of
these periods is less than the threshold, set $SmpDur_{next}=-1$ to indicate
stop sampling. Otherwise, calculate $SmpDur_{next}$ (line 16-21). The best
period, namely $T_{iter}$, is the period with the minimal error (line 15). If
$SmpDur_{next}>0$, we ignore $T_{iter}$, keep sampling, and call Algorithm 3
again after $SmpDur_{next}$. Otherwise, we use $T_{iter}$ for feature
measurement (Section 4.2).

Algorithm 3 Online robust period detection algorithm framework

Input:feature sampling sequence $\textbf{Smp}=\\{s_{1},\dots,s_{N}\\}$,
sampling interval $T_{s}$
Output:iterative period $T_{iter}$, next sampling duration $SmpDur_{next}$

1:$T_{init},err_{init}=$Algorithm1($\textbf{Smp},T_{s}$)

2:$SmpDur=(N-1)\times T_{s}$

3:if $SmpDur<c_{measure}\times T_{init}$ then

4: $T_{iter}=T_{init}$

5: $SmpDur_{next}=c_{measure}\times T_{init}-SmpDur$

6:end if

7:$t_{start}=max(0,(SmpDur-(2+c_{eval}\times step)\times T_{init}))$

8:while $(SmpDur-t_{start})/T_{init}\geq c_{measure}$ do

9: $istart=1+\lfloor t_{start}/T_{s}\rfloor$

10: $\textbf{SubSmp}=\\{s_{istart},\dots,s_{N}\\}$

11: $T_{j},err_{j}=$Algorithm1($\textbf{SubSmp},T_{s}$)

12: $t_{start}=t_{start}+step\times T_{init}$

13:end while

14:$T=\\{T_{j}\\},Err=\\{err_{j}\\}$

15:Find $min(Err)=err_{k}$ then $T_{iter}=T_{k}$

16:$Diff=abs((max(T)-min(T))/mean(T))$

17:if $Diff<Diff_{threshold}$ then

18: $SmpDur_{next}=-1$

19:else

20: $SmpDur_{next}=$

21:$\qquad\lceil SmpDur/max(T)\rceil\times max(T)-SmpDur$

22:end if

23:return $T_{iter},SmpDur_{next}$

Algorithm 4 Adaptive feature measurement

Input: features to be measured $FeatureName=\\{name_{1},\dots,name_{n}\\}$,
the feature for iterative period detection $\textbf{Feature}_{dect}$
Output: feature data $\textbf{Feature}=\\{feature_{1},\dots,feature_{n}\\}$

1:Start measurement for $FeatureName$ and $\textbf{Feature}_{dect}$

2:$SmpDur_{next}=SmpDur_{init}$

3:while $SmpDur_{next}>0$ do

4: Delay $SmpDur_{next}$

5: Collect sampling sequence of $\textbf{Feature}_{dect}$

6: $T_{iter},SmpDur_{next}=$Algorithm3$(\textbf{Feature}_{dect},T_{s})$

7:end while

8:Restart measurement for $FeatureName$

9:Delay $T_{iter}$ then stop measurement

10:Collect feature data Feature

11:return Feature

###  4.2 Micro-intrusive Online Feature Measurement

Based on the robust period detection, we propose the adaptive feature
measurement algorithm (Algorithm 4). The feature measurement causes overhead
and extends $T_{iter}$ compared with the normal run of the application. So, we
adaptively detect $T_{iter}$ of applications while the measurement is running
(line 1-7). In line 5, we collect $\textbf{Feature}_{dect}$ after a delay of
$SmpDur_{Next}$. We use the sampling sequence of $\textbf{Feature}_{dect}$ to
form the curve for the period detection, so we must sample
$\textbf{Feature}_{dect}$ continuously and uniformly. On the NVIDIA GPU
platform, the instantaneous power, SM utilization, and memory utilization can
meet this requirement. However, the performance counters cannot meet this
requirement because its minimum sampling granularity is a CUDA kernel.
According to our experimental results, we use the composite feature of power,
SM utilization, and memory utilization as $\textbf{Feature}_{dect}$, whose
traces show more obvious periodicity. In line 6, we call Algorithm 3 to detect
$T_{iter}$ and determine whether $T_{iter}$ is stable. If $SmpDur_{Next}>0$,
we redo line 4-6 with the new $SmpDur_{Next}$. Otherwise, we think $T_{iter}$
is stable and restart the feature measurement (line 8). After a delay of
$T_{iter}$, we stop measurement and collect the feature data (line 8-10).

We implement micro-intrusive online feature measurement based on Algorithm 4.
Users only need to insert the Begin and End APIs of GPOEO at the beginning and
end of their source code, rather than instrument loops.

###  4.3 Training Data Collection and Model Generation

We establish energy consumption and execution time prediction models with the
boosting machine learning method. Our work aims to find the optimal SM and
memory clock gears that optimize the objective function. Therefore, these four
models only need to predict the relative energy consumption and execution time
relative to the NVIDIA default scheduling strategy rather than the absolute
energy and time [4].

To train the models defined in Equation 1 and 2, we define and collect four
training data sets:

$EngTr_{SM}=\\{EngSM_{j}^{i}\\},\,\,TimeTr_{SM}=\\{TimeSM_{j}^{i}\\}$
$EngTr_{Mem}=\\{EngMem_{j}^{i}\\},\,\,TimeTr_{Mem}=\\{TimeMem_{j}^{i}\\}$

where $EngSM_{j}^{i}$ or $TimeSM_{j}^{i}$ represents a piece of training data
collected from application $i$ under the SM clock gear $SMgear_{j}$ and the
memory clock controlled by the NVIDIA default scheduling strategy.
$EngMem_{j}^{i}$ or $TimeMem_{j}^{i}$ is collected under the memory clock gear
$Memgear_{j}$ and the optimal SM clock gear. $eng_{default}^{i}$ and
$time_{default}^{i}$ are the default energy consumption and execution time
under the NVIDIA default scheduling strategy. Each input vector
${\textbf{w}_{SM}}_{j}^{i}$ or ${\textbf{w}_{Mem}}_{j}^{i}$ contains
$SMgear_{j}$ or $Memgear_{j}$ and the feature vector $\textbf{Feature}^{i}$.
For each application, the feature vector $\textbf{Feature}^{i}$ is measured
under the reference clock configuration.

$\displaystyle EngSM_{j}^{i}$
$\displaystyle=\\{{\textbf{w}_{SM}}_{j}^{i},{eng_{SM}}_{j}^{i}/eng_{default}^{i}\\}$
$\displaystyle TimeSM_{j}^{i}$
$\displaystyle=\\{{\textbf{w}_{SM}}_{j}^{i},{time_{SM}}_{j}^{i}/time_{default}^{i}\\}$
$\displaystyle{\textbf{w}_{SM}}_{j}^{i}$
$\displaystyle=\\{SMgear_{j},\textbf{Feature}^{i}\\}$ $\displaystyle
EngMem_{j}^{i}$
$\displaystyle=\\{{\textbf{w}_{Mem}}_{j}^{i},{eng_{Mem}}_{j}^{i}/eng_{default}^{i}\\}$
$\displaystyle TimeMem_{j}^{i}$
$\displaystyle=\\{{\textbf{w}_{Mem}}_{j}^{i},{time_{Mem}}_{j}^{i}/time_{default}^{i}\\}$
$\displaystyle{\textbf{w}_{Mem}}_{j}^{i}$
$\displaystyle=\\{Memgear_{j},\textbf{Feature}^{i}\\}$

####  4.3.1 Feature Selection

As mentioned in Section 2.2.4, the high-level features, such as power, SM
utilization, and memory utilization, cannot provide enough information for
modeling. So we introduce performance counter metrics as input features.

The CUPTI [15] supports profiling over 1100 performance counters on NVIDIA
high-end GPUs, such as RTX2080Ti and RTX3080Ti. Inspired by Arafa’s work [7],
we treat each Parallel Thread Execution (PTX) instruction as a basic unit of
energy consumption and focus on performance counter metrics that reflect the
density of different types of PTX instructions. We list the selected metrics
in Table II. A metric with prefix `sm__inst_executed_pipe_` represents a type
of PTX instruction. The suffix `pct_of_peak_sustained_active` means the
percentage of actual mean instruction throughput to the theoretical maximum
sustained instruction throughput in an activity clock cycle [15].

According to related work [4], DRAM and L2 cache miss information may help
predict energy and time. However, profiling performance counters of DRAM and
FBPA need several kernel replays which cannot be implemented online. We design
several composite metrics as alternatives, also shown in Table II. The
`L1MissPerInst` or `L2MissPerInst` means the number of L1 or L2 cache miss per
instruction. The `L1MissPct` or `L2MissPct` means the percentage of L1 or L2
cache miss. In conclusion, we use metrics listed in Table II as features.

TABLE II: Selected Features

Notation |  Full name or expression
---|---
IPCPct |  sm__inst_executed.PctSus
L1MissPerInst |  l1tex__t_sectors_lookup_miss.sum / sm__inst_executed.sum
L1MissPct |  l1tex__t_sectors_lookup_miss.sum / (l1tex__t_sectors_lookup_miss.sum + l1tex__t_sectors_lookup_hit.sum)
L2MissPerInst |  lts__t_sectors_lookup_miss.sum / sm__inst_executed.sum
L2MissPct |  lts__t_sectors_lookup_miss.sum / (lts__t_sectors_lookup_miss.sum + lts__t_sectors_lookup_hit.sum)
ALUPct |  sm__inst_executed_pipe_alu.PctSus
ADUPct |  sm__inst_executed_pipe_adu.PctSus
FP16Pct |  sm__inst_executed_pipe_fp16.PctSus
FMAPct |  sm__inst_executed_pipe_fma.PctSus
FP64Pct |  sm__inst_executed_pipe_fp64.PctSus
XUPct |  sm__inst_executed_pipe_xu.PctSus
TNSPct |  sm__inst_executed_pipe_tensor.PctSus
CBUPct |  sm__inst_executed_pipe_cbu.PctSus
LSUPct |  sm__inst_executed_pipe_lsu.PctSus
TEXPct |  sm__inst_executed_pipe_tex.PctSus
UNIPct |  sm__inst_executed_pipe_uniform.PctSus

_Note: PctSus = sum.pct_of_peak_sustained_active_

####  4.3.2 Benchmark Selection and Training Data Collection

We use the PyTorch Benchmarks [18], which contain over 40 mini ML
applications, for training. We select the AIBench Training Component Benchmark
[13], the benchmarking-gnns [16], a ThunderSVM [19] workload, and a ThunderGBM
[20, 21, 22] workload as the testing set. The benchmarking-gnns is a graph
neural networks (GNN) benchmarking framework including seven datasets (CLB,
CSL, SBM, TSP, TU, MLC, and SP) and nine models.

For each application in the training set, we profile features under the
reference clock configuration. We measure the actual energy
(${eng_{SM}}_{j}^{i}$) and time (${time_{SM}}_{j}^{i}$) under all available SM
clock gears and the memory clock controlled by the NVIDIA default scheduling
strategy. We also measure the actual energy (${eng_{Mem}}_{j}^{i}$) and time
(${time_{Mem}}_{j}^{i}$) under all available memory clock gears and the
optimal SM clock gear. Feature, energy, and time data construct four training
data sets ($EngTr_{SM}$, $TimeTr_{SM}$, $EngTr_{Mem}$, and $TimeTr_{Mem}$). We
conduct each measurement ten times and take the average to reduce the training
data noise.

####  4.3.3 Prediction model

We construct energy and time prediction models with the XGBoost [12], a widely
used supervised machine learning model improved from the gradient tree
boosting algorithm. Combined with our scenario, we apply the XGBoost to build
four prediction models shown in Equation 1 and 2. The model construction
processes are similar, so we take the energy consumption model $EngMdl_{SM}$
as an example to introduce these processes. For $EngMdl_{SM}$, the XGBoost
weights and sums several regression trees and can be defined as follows:

$\widehat{{eng_{SM}}_{j}^{i}}=\sum_{k=1}^{K}f_{k}({\textbf{w}_{SM}}_{j}^{i}),f_{k}\in\mathcal{F}$

where $\widehat{{eng_{SM}}_{j}^{i}}$ is the predicted energy consumption of
the input vector ${\textbf{w}_{SM}}_{j}^{i}$, which contains the features of
application $i$ and the SM gear $j$. $f_{k}$ represents the $k$th regression
tree, and $K$ is the number of regression trees. We use the training datasets
$EngTr_{SM}$ to train the model $EngMdl_{SM}$. During training, we use the
grid search method to tune the hyper-parameters such as the minimum loss
reduction, the maximum depth of a tree, the minimum sum of instance weight,
and the maximum number of nodes to be added.

####  4.3.4 Online Local Search

To fix minor errors caused by multi-objective predicted models, we perform a
local search around the predicted optimal clock configuration. We use online
detected period and energy data measured during one period to evaluate
different clock frequencies and find the actual optimal clock configuration.
We first conduct a local search for the memory clock because wrong memory
clock frequencies (too low) can lead to severe slowdowns. Based on the optimal
memory clock frequency, we conduct another local search for the SM clock.
According to our experimental results and Schwarzrock’s work [17], the
relationship between energy optimization objectives and clock gears is
generally a convex function. Based on this observation, we use the golden-
section search method [23] to accelerate our local search. We first find a
gear with a worse objective value on each side of the predicted optimal gear
to determine the search interval. Then we follow the classic golden section-
search process [23] to attempt different clock gears. Due to possible errors
of measured energy and periods, we fit the attempted points to obtain a convex
function. Then we use the convex function to determine the optimal clock gear.

Figure 5: The period detection errors of GPOEO and ODPP. GPOEO gives lower
errors compared to ODPP.

####  4.3.5 Optimize aperiodic applications

‘ The power and utilization traces of some applications are aperiodic, such as
applications in CSL and TUs datasets, the ThunderSVM [19] workload, and the
ThunderGBM [20, 21, 22] workload. We can not evaluate their execution time or
energy consumption with data measured in one period. In this case, we fix the
measurement time interval and the use measured mean number of instructions
executed per second (IPS) and power to evaluate the execution time and energy
consumption. If the number of instructions in the program is $Inst_{sum}$, the
execution time can be calculated as $time=Inst_{sum}/IPS$, and the energy
consumption can be calculated as $energy=power*time=Inst_{sum}*power/IPS$.
Then we can evaluate different clock frequency configurations.

Based on these analyses, we apply GPOEO to aperiodic applications. We first
measure performance counter metrics in the fixed time interval and predict the
optimal clock frequency configuration. In the online local search, we measure
and calculate $time_{default}$ and $energy_{default}$ under the NVIDIA default
scheduling strategy as the baseline. Then, we follow the golden-section search
strategy and collect $time_{i}$ and $energy_{i}$ under different clock
frequency configurations near the predicted optimal clock frequency
configuration. Finally, we compare these $time_{i}$ and $energy_{i}$ with the
baseline to find the optimal clock frequency configuration.

##  5 Evaluation

We evaluate our GPOEO system in this section. We first introduce the
experimental step. Then, we evaluate the accuracy of the period detection
algorithm and energy-performance prediction models. Finally, we analyze the
online energy-saving results on various ML benchmarks.

###  5.1 Experimental Setup

####  5.1.1 Hardware and Software Platforms

Our experimental platform is a GPU server equipped with one NVIDIA RTX3080Ti
GPU, one AMD 5950X CPU, and 64 GB memory. The software environment is NVIDIA
Driver 470.57 and CUDA 11.3. RTX3080Ti supports continuously adjustable SM
clock frequency, from 210 MHz to 2,025 MHz, and the step is 15 MHz. We find
that some higher frequencies are not practical or stable. Under lower
frequencies, applications cannot save energy while suffering severe slowdowns.
Therefore, we only consider the frequencies in the middle part, which can run
stably and may improve energy efficiency. We treat each SM clock frequency as
an SM clock gear, from $SMgear_{16}$ = 450 MHz to $SMgear_{114}$ = 1,920 MHz.
RTX3080Ti supports 5 global memory clock frequencies: $Memgear_{0}$ = 450 MHz,
$Memgear_{1}$ = 810 MHz, $Memgear_{2}$ = 5,001 MHz, $Memgear_{3}$ = 9,251 MHz,
and $Memgear_{4}$ = 9,501 MHz. We select $SMgear_{106}$ = 1,800 MHz and
$Memgear_{3}$ = 9,251 MHz as reference frequencies, which are used in
performance counter profiling.

####  5.1.2 Benchmarks

We train our machine learning models using data collected from PyTorch
Benchmarks [18]. We then test the trained models on AIBench [13] and
benchmarking-gnns [16]. In addition to deep neural networks, we also use two
classical ML workloads, the ThunderSVM [19] and ThunderGBM [20, 21, 22], in
our evaluation.

Figure 6: Period detection errors of ODPP and GPOEO on the CLB_GAT application
under different SM clock frequencies Figure 7: Period detection errors of ODPP
and GPOEO on the SBM_3WLGNN application under different SM clock frequencies
Figure 8: Period detection errors of ODPP and GPOEO on the TSP_GatedGCN
application under different SM clock frequencies

(a) Energy consumption prediction errors (b) Execution time prediction errors

Figure 9: Prediction errors by varying the SM clock (grouped by different SM
clock ranges)

(a) Energy consumption prediction errors (b) Execution time prediction errors

Figure 10: Prediction errors by varying the SM clock (grouped by different
datasets)

###  5.2 Accuracy and Sensitivity of Period Detection

We analyze our period detection algorithm on 34 different ML applications.
Figure 5 shows the period detection errors of GPOEO and ODPP [11] using the
NVIDIA default scheduling strategy. GPOEO is far more accurate than ODPP. The
mean period error of GPOEO is 1.72%, while the mean error of ODPP is 23.16%.
The maximum error of GPOEO is 7.2%, and 32 errors are within 5%. For ODPP,
nine errors are above 50%, nine errors are among 5-13%, and sixteen errors are
within 5%. GPOEO is more accurate than ODPP on 29 applications. For the other
three applications, the accuracy differences are within 1%.

(a) Energy consumption prediction errors (b) Execution time prediction errors

Figure 11: Prediction errors by varying the memory clock (grouped by different
memory clock frequencies)

(a) Energy consumption prediction errors (b) Execution time prediction errors

Figure 12: Prediction errors by varying the memory clock (grouped by different
datasets)

Figure 6, 7, and 8 show the periods detection errors of GPOEO and ODPP under
varying SM clock frequencies and fixed memory clock frequency. GPOEO exhibits
stable low errors (within 5% for most cases). This phenomenon indicates that
GPOEO is sensitive to clock frequency changes. However, ODPP shows poor
stability. On CLB_GAT and SBM_3WLGNN, ODPP gains huge errors under three and
ten SM clock frequencies, respectively. This instability causes inaccurate
prediction models, which ODPP builds online. For TSP_GatedGCN, ODPP gains huge
errors (nearly 100%) under all frequencies because it is disturbed by high-
frequency noise, only detects the local short period, and ignores the real
global period.

###  5.3 Accuracy of Energy and Execution Time Prediction

In this section, we evaluate four prediction models. We measure selected
features (Table II) during one iteration of each ML application under the
reference SM and memory clock frequency (1800 MHz and 9251MHz). Then we use
these features and different SM and memory clock frequencies as input of our
multi-objective models to predict the relative energy consumption and
execution time relative to the NVIDIA default scheduling strategy. Note that
for the SM clock models $EngMdl_{SM}$ and $TimeMdl_{SM}$, we let the NVIDIA
default scheduling strategy control the memory clock and then predict and
select the optimal SM clock frequency. For the memory models $EngMdl_{Mem}$
and $TimeMdl_{Mem}$, we assume that the SM clock is already set to the optimal
frequency and then predict and select the optimal memory clock frequency.

For the SM clock models, we collect 11,660 prediction values in total (2
objectives, 55 applications, and 106 SM clock frequencies). The mean
prediction errors of energy consumption and execution time are 3.05% and
2.09%, respectively. Next, we analyze the distributions of errors sorted by SM
clock frequency ranges and application datasets. Figure 9 shows the prediction
errors of energy consumption and execution time separately grouped by
different SM clock frequency ranges. Each clock frequency range contains 550
or 605 prediction values depending on the number of energy gears included in
the clock range (ten or eleven gears). For all clock ranges, most energy and
time prediction errors are less than 5%. Most scattered errors are within 20%.
This phenomenon proves that our energy prediction model and execution time
prediction model are accurate for different SM clock frequencies. Figure 10
shows the prediction errors grouped by different application datasets. Each
group contains 636 to 954 predicted values depending on the number of
applications included in the datasets (six to nine applications). For all
application datasets, most energy and execution time prediction errors are
less than 5%. This phenomenon demonstrates that our SM clock models are
applicable to all these applications.

For the memory clock models, we collect 550 prediction values in total (2
objectives, 55 applications, and 5 memory clock frequencies). The mean
prediction errors of energy consumption and execution time are 2.72% and
2.31%, respectively. Figure 11 shows the prediction errors of energy
consumption and execution time separately grouped by different memory clock
frequencies. For all clock frequencies, most energy and time prediction errors
are less than 5%. Figure 12 shows the prediction errors grouped by different
application datasets. For all application datasets, most prediction errors are
also within 5%. These phenomena demonstrate that our memory clock models are
applicable to all memory frequencies and all these applications.

Figure 13: Energy savings, slowdown, and ED2P saving compared to the NVIDIA default scheduling strategy on AIBench and traditional ML applications TABLE III: Online optimization process for SM and memory clock on AIBench | 3DFR | 3DOR | FE | I2IC | I2IP | I2T | ICMP | IGEN | LRK | OBJ | S2T | ST | T2T | TS
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Oracle SM Gear | 104 | 102 | 109 | 104 | 91 | 94 | 107 | 71 | 88 | 100 | 108 | 39 | 100 | 107
Prediction Error (SM gear) | -11 | 5 | -13 | 2 | 3 | -2 | -13 | 22 | 24 | -4 | -15 | 11 | 5 | -5
Search Error (SM gear) | -2 | -3 | -8 | 1 | -2 | 0 | -2 | -3 | -2 | 0 | -7 | 4 | -2 | -1
# of Search Steps (SM) | 5 | 4 | 4 | 3 | 4 | 3 | 6 | 8 | 9 | 4 | 5 | 5 | 4 | 4
Oracle Mem clock (MHz) | 9501 | 9251 | 9501 | 9501 | 9251 | 9251 | 9251 | 405 | 5001 | 9251 | 9251 | 810 | 9251 | 9501
Predicted Mem clock | 9501 | 9501 | 9251 | 9501 | 9501 | 9501 | 9501 | 405 | 5001 | 9251 | 9501 | 405 | 9251 | 9501
Searched Mem clock | 9501 | 9501 | 9501 | 9501 | 9501 | 9251 | 9251 | 405 | 5001 | 9251 | 9251 | 810 | 9251 | 9501
# of Search Steps (Mem) | 2 | 2 | 3 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 2 | 3 | 3 | 2

###  5.4 Results of Online Optimization

Our multi-objective models predict the energy consumption and execution time
of one iteration under different SM and memory clock gears. Users can use
diverse energy efficiency objectives to select the predicted optimal energy
gears and guide local search to find the actual optimal energy gears. In this
experiment, we set the objective function to minimize the energy consumption
within the slowdown constraint of 5%. For each ML training application, we use
the energy consumption and execution time under the NVIDIA default scheduling
strategy as the baseline. Then we run these applications with our GPOEO system
to optimize the energy consumption online. We also implement the ODPP [11] as
a comparison.

####  5.4.1 Medium benchmark suite

Figure 13 shows the online optimization results of the AIBench, the ThunderSVM
workload, and the ThunderGBM workload. We use energy saving, slowdown
(execution time increase), and $ED^{2}P$ ($ED^{2}P=Energy\times Time^{2}$)
saving to evaluate GPOEO and ODPP [11]. GPOEO achieves an average energy
saving of 14.7% and an average $ED^{2}P$ saving of 6.8%, with an average
execution time increase of 4.6%. Especially, GPOEO achieves significant energy
saving ($\geq 20\%$) on four out of sixteen applications. On AI_I2T, GPOEO
achieves 29.5% energy saving and 0.1% slowdown. Table III shows the online
optimization process for SM and memory clocks. On AI_I2T, the error of our
multi-objective prediction models is only -2 SM gears. This error is
eliminated by the online local search within five steps so that the vast
energy saving can be achieved. For AI_3DFR, AI_3DOR, AI_I2IP, and AI_TS, GPOEO
obtains considerable energy savings (18-24%) with reasonable slowdowns (less
than 8%). The online optimization processes of these applications are similar
to AI_I2T. The prediction errors of SM gear are relatively small (within 11 SM
gears), and the online local search reduces these errors in three to five
steps.

AI_FE, AI_ICMP, AI_IGEN, AI_LRK, AI_OBJ, AI_S2T, and AI_ST have medium energy-
saving opportunities (10-21%) with the slowdown constraint of 5%. GPOEO gains
medium energy savings (8-14%) with reasonable slowdowns (2-7%) on these seven
applications. Two reasons cause GPOEO does not make full use of energy-saving
potentials. For AI_FE and AI_S2T, the period detection and feature measurement
get inaccurate data due to some abnormal iterations. Therefore prediction
errors are significant and local search can not eliminate these errors. For
the convenience of experiments, we just train each machine learning model for
a few iterations, and only iterations after optimization processes can enjoy
the optimal SM gear. However, in real-life scenarios, the model will be
trained on many more iterations, for which our approach can give higher energy
saving. GPOEO does not perform well on AI_I2IC and AI_T2T. These two
applications are computation-intensive with little energy-saving opportunities
(1% and 4%). For non-periodical applications TGBM and TSVM, GPOEO also
achieves good results, saving 17.9% and 12.0% energy with slowdowns of 3.5%
and 4.7%, respectively. As for the memory clock, the oracle frequencies of
thirteen applications are 9,251 MHz or 9,501 MHz. Our method finds oracle
frequencies on eleven applications and finds nearby 9,501 MHz on the other two
applications within two or three search steps. In fact, the energy consumption
and execution time are similar under these two memory clock frequencies. GPOEO
also finds low oracle memory frequencies on AI_IGEN, AI_LRK, and AI_ST within
three steps. Our method meets the performance loss constraint of 5% on nine
applications, while ODPP only achieves the same goal on four applications. For
GPOEO, only iterations after optimization processes are guaranteed to meet the
performance loss constraint, and the previous iterations may result in a
violation of the performance loss constraint.

Figure 14: Energy saving, slowdown, and ED2P saving compared to the NVIDIA
default scheduling strategy on benchmarking-gnns applications

Compared to ODPP, our approach can improve the energy saving by 9.2%, improve
the $ED^{2}P$ saving by 20.4%, and reduce the slowdown by 5.0% on average.
GPOEO performs better than ODPP on all sixteen applications. Especially, our
approach gains both larger energy savings and lighter slowdowns on eight
applications. For AI_3DFR, AI_GEN, AI_LRK, and AI_S2T, GPOEO achieves more
considerable energy savings with similar slowdowns. Our method gains similar
energy savings with lighter slowdowns on AI_I2IC and TSVM. ODPP builds two
piecewise linear models online to predict energy and time. The accuracy of
these two models is highly dependent on the period detection accuracy. Poor
period detection accuracy of ODPP causes significant prediction errors, so
ODPP shows heavier slowdowns and less energy saving. On non-periodical
applications TGBM and TSVM, ODPP shows much worse results than GPOEO. This
phenomenon demonstrates that ODPP cannot handle non-periodical applications,
while GPOEO can.

####  5.4.2 Large benchmark suite

We also use the benchmarking-gnns suite to evaluate our method and ODPP [11]
extensively. Figure 14 shows the online optimization results of 55
applications in the benchmark-gnns. GPOEO achieves an energy saving of 16.6%
and an $ED^{2}P$ saving of 7.8%, with an execution time increase of 5.2% on
average. In comparison, ODPP gains an energy saving of 6.1% and an $ED^{2}P$
saving of -4.5%, with an execution time increase of 5.6% on average. GPOEO
saves $ED^{2}P$ on 50 applications, while ODPP only gains $ED^{2}P$ saving on
19 applications. Our method meets the performance loss constraint of 5% on 22
applications. ODPP achieves the same goal on 27 applications because it does
not profile performance counters and has a lower measurement overhead. With
the help of performance counter features, GPOEO saves more energy than ODPP on
48 applications. Applications in CSL and TU datasets are non-periodical. ODPP
can not handle these applications and only saves 0.73% of energy with a
slowdown of 1.32% on average. On the contrary, GPOEO gains an energy saving of
20.0% with a slowdown of 5.2% on average. These phenomena show that GPOEO has
better performance and broader applicability than ODPP.

Figure 15: Energy and time overhead of GPOEO on AIBench

###  5.5 Overhead Evaluation

To evaluate the overhead of the GPOEO system, we run AIBench applications with
the entire GPOEO system except adjusting SM and memory clocks. We also
manually set the number of local search steps shown in Table III. As shown in
Figure 15, all energy and time overheads are within 4%.

##  6 Related Work

There is a growing interest in optimizing machine learning workloads for
performance and energy efficiency. Many works concentrate on CPU energy
optimization [24, 25, 26, 27, 28, 17, 29]. Some of these prior works [24, 25,
26] use offline methods to model energy and performance, while others [27, 28,
17] design runtime to adjust the CPU clock or enforce power capping [29].
These methods rely heavily on run-time CPU-specific performance counter
profiling and are not transferable to GPUs, but the prediction models [30, 26,
28] they have used may also apply to GPUs.

Profiling workloads using GPU performance counter during program execution
time can be expensive. For this reason, most GPU energy optimization works
have to rely on offline profiling information [31, 4, 6, 7]. Most offline
works [31, 4, 6] focus on modeling and predicting energy and performance under
different hardware configurations. Other works study GPU energy and
performance from the view of assembly instructions [6, 7]. These works require
tedious offline profiling and analysis for each new application or even
different inputs. In contrast, our work can automatically optimize new
applications online once the prediction models are established and well
trained. Although these offline jobs are inconvenient to use, the energy
features [31, 4] they have used are instructive for GPU online energy
consumption optimization.

A few studies [10, 11] realize GPU online energy consumption optimization.
Majumdar _et al._ [10] exploit low-overhead fine-grained profiling functions
supported by the APU platform. It obtains the stream of energy, execution
time, throughput, and performance counter metrics at kernel granularity
without worrying about time and energy overhead. Therefore, it can catch
energy-saving chances at kernel granularity and save considerable energy with
low overhead. Majumdar’s work cannot be transplanted to the NVIDIA GPU
platform, considering the significant amount of code instrumentation (around
each kernel) and the high overhead of continuously profiling. Our approach
targets the NVIDIA GPU platform with high runtime profiling overhead (with a
slowdown of $>8\%$ and energy overhead of $>10\%$). We profile performance
counter metrics in only one iteration period to minimize overhead. ODPP [11]
proposes an online dynamic power-performance management framework for GPUs
using coarse-grained features which cannot provide enough information to model
energy consumption and performance accurately, as mentioned in Section 2.2.4.
Besides, the period detection algorithm of ODPP is unstable and error-prone.
Due to the two weaknesses, ODPP exhibits poor energy-saving results and can
give severe slowdown in our evaluation. Our approach exploits hardware
performance counter metrics and utilizes a robust period detection algorithm
to tackle these two weaknesses, leading to better performance.

Energy and performance optimization built upon machine learning techniques
have been demonstrated to be promising in various application domains [32, 33,
34, 35, 36, 37, 38, 39, 40, 41, 8, 42, 43, 9, 44, 45, 46, 47]. Some works [41,
8, 9, 44, 42, 46] tune hyperparameters, model structure configurations, or
data structures to speed up ML applications or save energy consumption. Our
method can be used together with these application-level techniques to reduce
energy consumption further. CAMEL [43] optimizes the energy of web
applications on mobile platforms. It uses the frame rate as the performance
index, which is only suitable for web applications. Many studies [35, 37, 32,
33, 36, 40, 45, 39, 38] concentrate on accelerating applications on
heterogeneous platforms. Combining these studies with our method may enable
acceleration while saving energy. Based on the graph neural network, Ye _et
al._ [47] propose a novel program analysis and modeling method to provide
comprehensive insight into the program. This method may be helpful to build
more accurate energy and performance prediction models.

##  7 Conclusion

We have presented GPOEO, a new online GPU energy optimization framework for
iterative machine learning (ML) workloads. GPOEO detects iterative periods,
measures performance counter features, and predicts the optimal energy
configurations automatically. We evaluate GPOEO on 71 ML applications running
on an NVIDIA RTX3080Ti GPU. GPOEO achieves a mean energy saving of 16.2% at a
modest cost of 5.1% performance loss compared to the NVIDIA default scheduling
strategy.

## Acknowledgments

This work was supported in part by the National Key Research and Development
Program of China (2020YFB1406902), the Key-Area Research and Development
Program of Guangdong Province (2020B0101360001), the Shenzhen Science and
Technology Research and Development Foundation (JCYJ20190806143418198), the
National Natural Science Foundation of China (NSFC) (61872110 and 61872294),
the Fundamental Research Funds for the Central Universities (Grant No.
HIT.OCEF.2021007), the Peng Cheng Laboratory Project (PCL2021A02), and the
CCF-Huawei fund (CCF-HuaweiHP2021002). Professor Weizhe Zhang is the
corresponding author.

## References

  * [1] Y. LeCun, Y. Bengio, and G. Hinton, “Deep learning,” _nature_ , vol. 521, no. 7553, pp. 436–444, 2015.
  * [2] M. Z. Alom, T. M. Taha, C. Yakopcic, S. Westberg, P. Sidike, M. S. Nasrin, M. Hasan, B. C. Van Essen, A. A. Awwal, and V. K. Asari, “A state-of-the-art survey on deep learning theory and architectures,” _Electronics_ , vol. 8, no. 3, p. 292, 2019.
  * [3] J. Guerreiro, A. Ilic, N. Roma, and P. Tomas, “Gpgpu power modeling for multi-domain voltage-frequency scaling,” in _2018 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 2018, pp. 789–800.
  * [4] ——, “Modeling and decoupling the gpu power consumption for cross-domain dvfs,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 30, no. 11, pp. 2494–2506, 2019.
  * [5] ——, “Dvfs-aware application classification to improve gpgpus energy efficiency,” _Parallel Computing_ , vol. 83, pp. 93–117, 2019.
  * [6] ——, “Gpu static modeling using ptx and deep structured learning,” _IEEE Access_ , vol. 7, pp. 159 150–159 161, 2019.
  * [7] Y. Arafa, A. ElWazir, A. ElKanishy, Y. Aly, A. Elsayed, A.-H. Badawy, G. Chennupati, S. Eidenbenz, and N. Santhi, “Verified instruction-level energy consumption measurement for nvidia gpus,” in _Proceedings of the 17th ACM International Conference on Computing Frontiers_ , 2020, pp. 60–70.
  * [8] Y. Wang, Q. Wang, and X. Chu, “Energy-efficient inference service of transformer-based deep learning models on gpus,” in _2020 International Conferences on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData) and IEEE Congress on Cybermatics (Cybermatics)_. IEEE, 2020, pp. 323–331.
  * [9] S. M. Nabavinejad, S. Reda, and M. Ebrahimi, “Batchsizer: Power-performance trade-off for dnn inference,” in _Proceedings of the 26th Asia and South Pacific Design Automation Conference_ , 2021, pp. 819–824.
  * [10] A. Majumdar, L. Piga, I. Paul, J. L. Greathouse, W. Huang, and D. H. Albonesi, “Dynamic gpgpu power management using adaptive model predictive control,” in _2017 IEEE International Symposium on High Performance Computer Architecture (HPCA)_. IEEE, 2017, pp. 613–624.
  * [11] P. Zou, L. Ang, K. Barker, and R. Ge, “Indicator-directed dynamic power management for iterative workloads on gpu-accelerated systems,” in _2020 20th IEEE/ACM International Symposium on Cluster, Cloud and Internet Computing (CCGRID)_. IEEE, 2020, pp. 559–568.
  * [12] T. Chen and C. Guestrin, “Xgboost: A scalable tree boosting system,” in _Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining_ , 2016, pp. 785–794.
  * [13] F. Tang, W. Gao, J. Zhan, C. Lan, X. Wen, L. Wang, C. Luo, Z. Cao, X. Xiong, Z. Jiang _et al._ , “Aibench training: balanced industry-standard ai training benchmarking,” in _2021 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)_. IEEE, 2021, pp. 24–35.
  * [14] NVIDIA Corporation, “Nvml api reference manual,” https://docs.nvidia.com/deploy/nvml-api/index.html, August 2021, accessed August 19, 2021.
  * [15] ——, “Cupti documentation,” https://docs.nvidia.com/cupti/Cupti/index.html, August 2021, accessed August 19, 2021.
  * [16] V. P. Dwivedi, C. K. Joshi, T. Laurent, Y. Bengio, and X. Bresson, “Benchmarking graph neural networks,” _arXiv preprint arXiv:2003.00982_ , 2020.
  * [17] J. Schwarzrock, C. C. de Oliveira, M. Ritt, A. F. Lorenzon, and A. C. S. Beck, “A runtime and non-intrusive approach to optimize edp by tuning threads and cpu frequency for openmp applications,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 7, pp. 1713–1724, 2020.
  * [18] pytorch.org, “Pytorch benchmarks,” https://github.com/pytorch/benchmark, August 2021, accessed August 19, 2021\.
  * [19] Z. Wen, J. Shi, Q. Li, B. He, and J. Chen, “ThunderSVM: A fast SVM library on GPUs and CPUs,” _Journal of Machine Learning Research_ , vol. 19, pp. 797–801, 2018.
  * [20] Z. Wen, J. Shi, B. He, J. Chen, K. Ramamohanarao, and Q. Li, “Exploiting gpus for efficient gradient boosting decision tree training,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 30, no. 12, pp. 2706–2717, 2019.
  * [21] Z. Wen, J. Shi, B. He, Q. Li, and J. Chen, “ThunderGBM: Fast GBDTs and random forests on GPUs,” _Journal of Machine Learning Research_ , vol. 21, 2020.
  * [22] Z. Wen, J. Shi, B. He, J. Chen, K. Ramamohanarao, and Q. Li, “Exploiting gpus for efficient gradient boosting decision tree training,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 30, no. 12, pp. 2706–2717, 2019.
  * [23] H. Walser, _The golden section_. MAA, 2001.
  * [24] M. Endrei, C. Jin, M. N. Dinh, D. Abramson, H. Poxon, L. DeRose, and B. R. de Supinski, “Statistical and machine learning models for optimizing energy in parallel applications,” _The International Journal of High Performance Computing Applications_ , vol. 33, no. 6, pp. 1079–1097, 2019.
  * [25] S. Ramesh, S. Perarnau, S. Bhalachandra, A. D. Malony, and P. Beckman, “Understanding the impact of dynamic power capping on application progress,” in _2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 2019, pp. 793–804.
  * [26] M. Hao, W. Zhang, Y. Wang, G. Lu, F. Wang, and A. V. Vasilakos, “Fine-grained powercap allocation for power-constrained systems based on multi-objective machine learning,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 32, no. 7, pp. 1789–1801, 2020.
  * [27] N. Gholkar, F. Mueller, and B. Rountree, “Uncore power scavenger: A runtime for uncore power conservation on hpc systems,” in _Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis_ , 2019, pp. 1–23.
  * [28] Y. Wang, W. Zhang, M. Hao, and Z. Wang, “Online power management for multi-cores: A reinforcement learning based approach,” _IEEE Transactions on Parallel and Distributed Systems_ , 2021.
  * [29] P. Petoumenos, L. Mukhanov, Z. Wang, H. Leather, and D. S. Nikolopoulos, “Power capping: What works, what does not,” in _2015 IEEE 21st International Conference on Parallel and Distributed Systems (ICPADS)_. IEEE, 2015, pp. 525–534.
  * [30] M. Endrei, C. Jin, M. N. Dinh, D. Abramson, H. Poxon, L. DeRose, and B. R. de Supinski, “Energy efficiency modeling of parallel applications,” in _SC18: International Conference for High Performance Computing, Networking, Storage and Analysis_. IEEE, 2018, pp. 212–224.
  * [31] K. Fan, B. Cosenza, and B. Juurlink, “Predictable gpus frequency scaling for energy and performance,” in _Proceedings of the 48th International Conference on Parallel Processing_ , 2019, pp. 1–10.
  * [32] Z. Wang and M. F. O’Boyle, “Mapping parallelism to multi-cores: a machine learning based approach,” in _Proceedings of the 14th ACM SIGPLAN symposium on Principles and practice of parallel programming_ , 2009, pp. 75–84.
  * [33] D. Grewe, Z. Wang, and M. F. O’Boyle, “Portable mapping of data parallel programs to opencl for heterogeneous systems,” in _Proceedings of the 2013 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)_. IEEE, 2013, pp. 1–10.
  * [34] Z. Wang, D. Grewe, and M. F. O’boyle, “Automatic and portable mapping of data parallel programs to opencl for gpu-based heterogeneous systems,” _ACM Transactions on Architecture and Code Optimization (TACO)_ , vol. 11, no. 4, pp. 1–26, 2014.
  * [35] C. Cummins, P. Petoumenos, Z. Wang, and H. Leather, “End-to-end deep learning of optimization heuristics,” in _2017 26th International Conference on Parallel Architectures and Compilation Techniques (PACT)_. IEEE, 2017, pp. 219–232.
  * [36] Y. Wen, Z. Wang, and M. F. O’boyle, “Smart multi-task scheduling for opencl programs on cpu/gpu heterogeneous platforms,” in _2014 21st International conference on high performance computing (HiPC)_. IEEE, 2014, pp. 1–10.
  * [37] B. Taylor, V. S. Marco, and Z. Wang, “Adaptive optimization for opencl programs on embedded heterogeneous systems,” in _Proceedings of the 18th ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems_ , 2017, pp. 11–20.
  * [38] Z. Wang and M. O’Boyle, “Machine learning in compiler optimization,” _Proceedings of the IEEE_ , vol. 106, no. 11, pp. 1879–1901, 2018.
  * [39] J. Fang, C. Huang, T. Tang, and Z. Wang, “Parallel programming models for heterogeneous many-cores: a comprehensive survey,” _CCF Transactions on High Performance Computing_ , vol. 2, no. 4, pp. 382–400, 2020.
  * [40] P. Zhang, J. Fang, T. Tang, C. Yang, and Z. Wang, “Auto-tuning streamed applications on intel xeon phi,” in _2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS)_. IEEE, 2018, pp. 515–525.
  * [41] D. Stamoulis, E. Cai, D.-C. Juan, and D. Marculescu, “Hyperpower: Power-and memory-constrained hyper-parameter optimization for neural networks,” in _2018 Design, Automation & Test in Europe Conference & Exhibition (DATE)_. IEEE, 2018, pp. 19–24.
  * [42] V. S. Marco, B. Taylor, Z. Wang, and Y. Elkhatib, “Optimizing deep learning inference on embedded systems through adaptive model selection,” _ACM Transactions on Embedded Computing Systems (TECS)_ , vol. 19, no. 1, pp. 1–28, 2020.
  * [43] J. Ren, L. Yuan, P. Nurmi, X. Wang, M. Ma, L. Gao, Z. Tang, J. Zheng, and Z. Wang, “Camel: Smart, adaptive energy optimization for mobile web interactions,” in _IEEE INFOCOM 2020-IEEE Conference on Computer Communications_. IEEE, 2020, pp. 119–128.
  * [44] A. E. Brownlee, J. Adair, S. O. Haraldsson, and J. Jabbo, “Exploring the accuracy–energy trade-off in machine learning,” in _2021 IEEE/ACM International Workshop on Genetic Improvement (GI)_. IEEE, 2021, pp. 11–18.
  * [45] P. Zhang, J. Fang, C. Yang, C. Huang, T. Tang, and Z. Wang, “Optimizing streaming parallelism on heterogeneous many-core architectures,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 31, no. 8, pp. 1878–1896, 2020.
  * [46] S. Qiu, L. You, and Z. Wang, “Optimizing sparse matrix multiplications for graph neural networks,” in _Lecture Notes in Computer Science_. Springer Verlag, 2021.
  * [47] G. Ye, Z. Tang, H. Wang, D. Fang, J. Fang, S. Huang, and Z. Wang, “Deep program structure modeling through multi-relational graph-based learning,” in _Proceedings of the ACM International Conference on Parallel Architectures and Compilation Techniques_ , 2020, pp. 111–123.


# AUTOHOMEOMORPHISMS OF THE FINITE POWERS OF THE DOUBLE ARROW.

Sebastián Barría, Carlos Martinez-Ranero 111Universidad de Concepción, Chile
(all authors).

###### Abstract

Let $\mathbb{A}$ and $\mathbb{S}$ denote the double arrow of Alexandroff and
the Sorgenfrey line, respectively. We show that any homeomorphism
$h:^{m}\mathbb{A}\to^{m}\mathbb{A}$ is locally (outside of a nowhere dense
set) a product of monotone embeddings
$h_{i}:J_{i}\subseteq\mathbb{A}\to\mathbb{A}(i\in m)$ followed by a
permutation of the coordinates.
We also prove that the symmetric products $\mathcal{F}_{m}(\mathbb{A})$ are
not homogeneous for any $m\geq 2$. This partially solves an open question of
A. Arhangel’skiǐ [Ar87]. In contrast, we show that symmetric product
$\mathcal{F}_{2}(\mathbb{S})$ is homogeneous. 222The first named author was
partially supported by CONICYT-PFCHA Doctorado Nacional 2017-21170738. The
second named author was partially supported by Proyecto VRID-Investigación No.
220.015.024-INV

Keywords: Double arrow, hyperspaces, homogeneous spaces, Sorgenfrey.

MSC2020: 54B20, 54B10, 54F05

###### Contents

  1. 1 INTRODUCTION
  2. 2 AUTOHOMEOMORPHISMS OF ${}^{m}\mathbb{A}$
  3. 3 NON-HOMOGENEITY OF $\mathcal{F}_{m}(\mathbb{A})$
  4. 4 HOMOGENEITY OF $\mathcal{F}_{2}(\mathbb{S})$.

##  1 INTRODUCTION

A space $X$ is homogeneous if for every $x,y\in X$ there exists a
autohomeomorphism $h$ of $X$ such that $h(x)=y$. Several classic results on
homogeneity involve the study of the hyperspace $Exp(X)$ (set of closed
subsets of $X$) in the Vietoris topology. In this paper we are motivated by
the following general question.

######  Question 1.1.

When is $\operatorname{Exp}(X)$ homogeneous?

In the seventies, it was shown by Shori and West [SW75] that
$\operatorname{Exp}([0,1])$ is homeomorphic to the Hilbert’s cube. In
particular, is possible that the $\operatorname{Exp}(X)$ is homogeneous while
$X$ is not. On the other hand, if $\kappa>\aleph_{1}$, then
$\operatorname{Exp}{(2^{\kappa})}$ is not homogeneous (see [Sce76]). Thus, the
question of homogeneity of the hyperspace turns out to be quite subtle.

Arhangel’skiǐ in [Ar87] asked the following question (it also appears in
[AvM13]).

######  Question 1.2.

Is the hyperspace $\operatorname{Exp}{(\mathbb{A})}$ homogeneous?

In this paper we partially answer Question 1.2, by showing that.

######  Theorem 1.3.

The symmetric product $\mathcal{F}_{m}(\mathbb{A})$ is not homogeneous for any
$m\geq 2$.

Where the symmetric product $\mathcal{F}_{m}(\mathbb{A})$ is the subspace of
$\operatorname{Exp}(\mathbb{A})$ consisting of all finite, non-empty, subsets
of cardinality at most $m$.

The following result can be seen as a companion of the previous Theorem.

######  Theorem 1.4.

The symmetric product $\mathcal{F}_{2}(\mathbb{S})$ is homeomorphic to
$\mathbb{S}^{2}$. In particular, it is homogeneous.

In the course of proving Theorem 1.3, we study the group of autohomeomorphisms
of ${}^{m}\mathbb{A}$, and obtain the following Theorem which give us a
complete picture on the structure of such autohomeomorphisms.

######  Theorem 1.5.

Let $h:^{m}\mathbb{A}\to^{m}\mathbb{A}$ be a homeomorphism. Then there is a
pairwise disjoint sequence of basic clopen boxes $U_{n}:=\prod\limits_{j\in
m}I^{j}_{n}(n\in\omega)$ such that $\bigcup U_{n}$ is dense in
${}^{m}\mathbb{A}$ and $h\restriction U_{n}=\sigma\circ
h^{0}\times\cdots\times h^{m-1},$ where each $h^{j}:I_{n}^{j}\to\mathbb{A}$ is
an strictly monotone homeomorphism onto a clopen interval, and $\sigma$ is a
permutation of ${}^{m}\mathbb{A}$.

The paper is organized as follows. In Section 2 we study the
autohomeomorphisms of ${}^{m}\mathbb{A}$ and give a proof of Theorem 1.5. In
Section 3 we give a proof of Theorem 1.3 and in Section 4 a proof of Theorem
1.4. The notation and terminology in this paper is fairly standard. We will
use [En89] as a basic reference on topology and [AvM13] as a reference for
homogeneity and hyperspaces.

##  2 AUTOHOMEOMORPHISMS OF ${}^{m}\mathbb{A}$

The purpose of this section it to prove Theorem 1.5. It will be convenient to
introduce some notation. Let
$\mathbb{A}_{0}=]0,1]\times\\{0\\},\mathbb{A}_{1}=[0,1[\times\\{1\\}$ and
$\mathbb{A}=\mathbb{A}_{0}\cup\mathbb{A}_{1}$. Define the lexicographical
ordering $\langle a,r\rangle\prec\langle b,s\rangle$ if $a<b$ or $a=b$ and
$r<s$. The set $\mathbb{A}$ with the order topology is the double arrow space.

The Let $\pi:\mathbb{A}\to[0,1]$ be the projection onto the first factor
$\pi(\langle x,r\rangle)=x$, we will think of an element of the finite power
$x\in^{m}\mathbb{A}$ as function $x:m\to\mathbb{A}$. For any $a\in\mathbb{A}$
we will denote by $\overline{a}$ the constant sequence $a$ of arbitrary finite
length. Let $\pi_{i}:^{m}\mathbb{A}\to\mathbb{A}$ be the projection onto the
$i$-coordinate, and let $h_{i}=\pi_{i}\circ h$. Recall that a partial function
$f:\mathbb{A}\to\mathbb{A}$ is monotone if it is either non-decreasing or non-
increasing, and $f$ is strictly monotone if it is either strictly increasing
or strictly decreasing.

We now recall the following result from R. Hernández-Gutiérrez.

######  Proposition 2.1 ([HG13] Proposition 3.1).

Let $h:\mathbb{A}\to\mathbb{A}$ be a continuous function, then there exists a
pairwise disjoint sequence $J_{n}(n\in\omega)$ of clopen intervals such that
$\bigcup_{n\in\omega}J_{n}$ is dense in $\mathbb{A}$, and $h\restriction
J_{n}$ is monotone, for any $n\in\omega.$

The following proposition tell us how continuous monotone functions look like
locally.

######  Proposition 2.2.

Let $h:\mathbb{A}\to\mathbb{A}$ be a monotone continuous function. Then there
is a clopen interval $J$ so that either $h\restriction J$ is constant or
$h\restriction J$ is strictly monotone.

###### Proof.

On one hand, if there is a clopen interval $J$ so that $h\restriction J$ is an
injection, then there is nothing to prove. On the other hand, if there are
$x,y\in\mathbb{A}$ so that $\pi(x)\neq\pi(y)$ and $h(x)=h(y)$, then we are
similarly finished. If neither of the above alternatives hold, then there
exists a dense set $D\subset\mathbb{A}\times\\{\langle 0,1\rangle\\}$ so that
$h\restriction(\mathbb{A}\setminus D)$ is strictly monotone and $h(\langle
a,0\rangle)=h(\langle a,1\rangle)$ for any $\langle a,0\rangle\in\mathbb{A}.$
However, such a function cannot be continuous. This finishes the proof of the
Lemma. ∎

######  Definition 2.3.

Let $h:\mathbb{A}\to^{m}\mathbb{A}$ and $j_{0}\in m$ be given. We say that a
clopen interval $J$ is $j_{0}$-good for $h$ if $h_{j_{0}}\restriction J$ is
strictly monotone and $h_{j}\restriction J$ is constant for any $j\in
m\setminus\\{j_{0}\\}$. We say that $J$ is good for $h$ if it is $j_{0}$-good
for some $j_{0}\in m$.

######  Remark 2.4.

In other words, $J$ is $j_{0}$-good for $h$ if and only if $h$ sends $J$ into
a line parallel to the $j_{0}$-th axis.

The following lemma gives an indication as to why this definition will play a
role. It will be used in the verification of Theorem 1.5.

######  Lemma 2.5.

Let $h:\mathbb{A}\to^{m}\mathbb{A}$ be an embedding such that
$h^{\prime\prime}[\mathbb{A}]$ is $G_{\delta}$ in ${}^{m}\mathbb{A}$. Then
there exists a pairwise disjoint sequence $J_{n}(n\in\omega)$ of clopen
intervals such that $\bigcup_{n\in\omega}J_{n}$ is dense in $\mathbb{A}$ and
for each $n,$ there is $j\in m$ so that $J_{n}$ is $j$-good for $h$.

###### Proof.

Let $U$ denote the union of all clopen intervals which are good for $h$. Since
$\mathbb{A}$ is separable, it suffices to show that $U$ is dense. In order to
get a contradiction, suppose that there is a nonempty clopen interval $J$
disjoint from $U$. By going to a clopen sub-interval of $J$ if necessary, and
applying, Proposition 2.1 and Lemma 2.2, $m$ times, we may assume that
$h_{j}\restriction J$ is either one-to-one or constant, for any $j\in m$.
Since $h$ is an embedding there is at least one $j\in m,$ such that $h_{j}$ is
non-constant (equivalently, strictly monotone). Therefore, we are left to show
that there is at most one $j\in m$ so that $h_{j}$ is non-constant.

######  Claim 2.6.

If there exists $j_{0}\neq j_{1}\in m$ such that $h_{j_{0}}\restriction J$ and
$h_{i_{1}}\restriction J$ are one-to-one, then $X=h"[J]$ is not a $G_{\delta}$
in ${}^{m}\mathbb{A}$.

###### Proof.

Let $X\subseteq\bigcap_{n\in\omega}U_{n},$ where each $U_{n}$ is an open set.
Since $X$ is compact, we may assume, that $U_{n}=\bigcup_{i\in
k_{n}}\prod\limits_{j\in m}I_{n,i}^{j},$ where $I_{n,i}^{j}$ are clopen
intervals. Let $A$ be equal to

$\\{\pi(x):\exists n\in\omega\exists i\leq
k_{n},j\in\\{j_{0},j_{1}\\}(x\in\\{\min(I_{n,i}^{j}),\max(I_{n,i}^{j})\\})\\}$

Fix $x\in X$ so that $\pi(x(i_{0}))$ does not belong to $A$, this is possible
as $A$ is countable and $h_{i_{0}}\restriction J$ is an injection. We claim
that both points

$x\restriction(m\setminus\\{i_{0}\\})\cup\\{(i_{0},\langle\pi(x),0\rangle)\\}\
\rm{and}\
x\restriction(m\setminus\\{i_{0}\\})\cup\\{(i_{0},\langle\pi(x),1\rangle)\\}$

belong to $\bigcap_{n\in\omega}U_{n}.$ However, only one of them belongs to
$X$ as $h_{j_{1}}$ is injective, which is a contradiction. In order to prove
the claim, fix $N\in\omega.$ As $x\in X\subseteq\bigcap_{n\in\omega}U_{n}.$ We
can find $i\in k_{n}$ so that $x\in\prod\limits_{j\in m}I_{N,i}^{j}$. Note
that, $\langle\pi(x(i_{0})),0\rangle$ and $\langle\pi(x(i_{0})),1\rangle,$
both belong to $I_{N,i}^{j_{0}}$, as neither of them are the maximum nor the
minimum. Thus,
$x\restriction(m\setminus\\{i_{0}\\})\cup\\{(i_{0},\langle\pi(x),0\rangle)\\}$
and
$x\restriction(m\setminus\\{i_{0}\\})\cup\\{(i_{0},\langle\pi(x),1\rangle)\\}$
belong to $U_{N}$ as required. This finishes the proof of the Claim. ∎

Observe that since $h^{\prime\prime}[\mathbb{A}]$ is a $G_{\delta}$ in
${}^{m}\mathbb{A}$ and $J$ is clopen in $\mathbb{A}$, it follows that $X$ is
also a $G_{\delta}$ in ${}^{m}\mathbb{A}$, which contradicts the previous
Claim.

∎

We are now ready to prove the main Theorem of the section.

######  Theorem 2.7.

Let $h:^{m}\mathbb{A}\to^{m}\mathbb{A}$ be a homeomorphism. Then there is a
pairwise disjoint sequence of basic clopen boxes $U_{n}:=\prod\limits_{j\in
m}I^{j}_{n}(n\in\omega)$ such that $\bigcup U_{n}$ is dense in
${}^{m}\mathbb{A}$ and $h\restriction U_{n}=\sigma\circ
h^{0}\times\cdots\times h^{m-1},$ where each $h^{j}:I_{n}^{j}\to\mathbb{A}$ is
an strictly monotone homeomorphism onto a clopen interval, and $\sigma$ is a
permutation of ${}^{m}\mathbb{A}$.

###### Proof.

Since ${}^{m}\mathbb{A}$ is separable, and every clopen box is homeomorphic to
${}^{m}\mathbb{A}$ via a product of strictly increasing homeomorphisms. Thus,
it suffices to show that there is a clopen box so that $h$ restricted to it is
as desired. For each $a\in^{m-1}\mathbb{A}$ and $i\in m,$ define the line
$E_{a,i}=\\{x\in^{m}\mathbb{A}:x\restriction(m\setminus\\{i\\})=a\\}$, and
define an embedding $e_{a,i}:\mathbb{A}\to^{m}\mathbb{A}$ by
$e_{a,i}(p)=a\cup\\{(i,p)\\}$. Note that $h^{\prime\prime}[E_{a,i}]$ is a
$G_{\delta}$ in ${}^{m}\mathbb{A},$ since $E_{a,i}$ is $G_{\delta}$ in
${}^{m}\mathbb{A}$, and $h$ is a homeomorphism. We will recursively construct,
for $j\in m$, clopen boxes $V_{j}:=\prod\limits_{i\in
m}J_{i}^{j}\subset^{m}\mathbb{A}$ and functions $\sigma_{j}:\\{0,\dots,j\\}\to
m$ such that

  1. i.

$V_{j+1}\subset V_{j}$ for $j\in m-1.$

  2. ii.

For each $i<j$ and $a\in\pi_{m-\\{i\\}}^{\prime\prime}[V_{j}]$, $I^{j}_{i}$ is
$\sigma(i)$-good for $h\circ e_{a,i}$.

  3. iii.

$\sigma_{j+1}\restriction j=\sigma_{j}$ and $\sigma_{i}$ is injective for
$j\in m-1.$

Suppose we have constructed $V_{j},\sigma_{j}$ for $j<k\leq m$. By applying
Lemma 2.5 to the map $h\circ e_{a,k}\restriction I^{k-1}_{i}$, we can find for
each $a\in A:=\pi_{m-\\{k\\}}^{\prime\prime}[V_{k-1}],$ rationals
$q_{a},r_{a}\in\mathbb{Q}$ and an integer $j_{a,k}$ such that $[\langle
q_{a},1\rangle,\langle r_{a},0\rangle])\subset I^{k-1}_{i}$ is $j_{a,k}$-good
for $h\circ e_{a,k}$. Since $A$ is a Baire space, there exists $j_{0},q,r$
such that $A_{j_{0},q,r}:=\\{x\in A:q_{x}=q,r_{x}=r,j_{x,0}=j_{0}\\}$ is dense
in some clopen box $V:=J_{0}\times\cdots\times J_{m-1}\subseteq A$.

######  Claim 2.8.

The interval $[\langle q,1\rangle,\langle r,0\rangle]$ is $j_{0}$-good, for
$h\circ e_{x,k}$ for any $x\in V$.

###### Proof.

We must show that $h_{j}\circ e_{x,k}\restriction[\langle q,1\rangle,\langle
r,0\rangle]$ is constant for any $j\in m\setminus\\{j_{0}\\}$. In order to do
so, pick $j\in m\setminus\\{j_{0}\\},x\in V$ and $s,t\in[\langle
q,1\rangle,\langle r,0\rangle]$. Choose a sequence $x_{n}$ of elements of
$A_{j_{0},q,r}$ converging to $x$, this is possible as $A_{j_{0},q,r}$ is
dense in $V$. Notice that $e_{x_{n},k}(s)$ and $e_{x_{n},k}(t)$ converge to
$e_{x,k}(s)$ and $e_{x,k}(t)$, respectively. By assumption, we have that
$h_{i}(e_{x,k}(s))=\lim\limits_{n\to\infty}h_{i}(e_{x_{n},k}(s))=\lim\limits_{n\to\infty}h_{i}(e_{x_{n},k}(t))=h_{i}(e_{x,k}(t)).$
∎

Define

$V_{k}=J_{0}\times\dots\times J_{k-1}\times[\langle q,1\rangle,\langle
r,0\rangle]\times J_{k+1}\times\dots\times J_{m-1}\ \rm{and}\
\sigma_{k}=\sigma_{k-1}\cup\\{(k,j_{0})\\}.$

It follows from the previous claim that properties i. and ii. hold and also
clearly $\sigma_{k}$ extends $\sigma_{k-1}$. Hence, we are left to show that
$\sigma_{k}$ is injective. Suppose for a contradiction that
$\sigma_{k}(i_{0})=\sigma_{k}(i_{1})$ for some $i_{0}\neq i_{1}$. Pick $a\neq
b\in V_{k}$ so that

$a^{i_{0}}:=a\restriction m-\\{i_{0}\\}=b\restriction
m-\\{i_{0}\\}=:b^{i_{0}},\ \rm{and\ let}\ a^{i_{1}}=a\restriction
m-\\{i_{1}\\},b^{i_{1}}=b\restriction m-\\{i_{1}\\}.$

Notice that $|E_{a^{i_{0}},i_{0}}\cap E_{a^{i_{1}},i_{1}}|=1.$ Hence, it
follows that $h^{\prime\prime}[E_{a^{i_{0}},i_{0}}\cap V_{k}]\subset
E_{h(a)^{i_{0}},\sigma(i_{0})}$ and also
$h^{\prime\prime}[E_{a^{i_{1}},i_{1}}\cap V_{k}]\subset
E_{h(a)^{i_{1}},\sigma(i_{1})}.$ By assumption,
$E_{h(a)^{i_{0}},\sigma(i_{0})}=E_{h(a)^{i_{1}},\sigma(i_{1})}.$ However, this
would imply that $h^{\prime\prime}[E_{a^{i_{1}},i_{1}}\cap V_{k}]\cap
h^{\prime\prime}[E_{b^{i_{0}},i_{0}}\cap V_{k}]=\emptyset$, which contradicts
the fact that $|E_{a^{i_{1}},i_{1}}\cap E_{b^{i_{0}},i_{0}}\cap V_{k}|=1.$
Finally, let $\sigma=\sigma_{m-1}$ and let $h^{j}=h_{j}\circ
e_{a^{j},j}\restriction I^{k}_{j}$ for some fixed $a\in V_{k}$ and $j\in m$.
It follows from our construction that $h\restriction V_{k}=\sigma\circ
h^{0}\times\dots\times h^{m}$ as required. ∎

The previous Theorem give us an a posteriori explanation of why the space
${}^{m}\mathbb{A}$ is not countable dense homogeneous for any $m\geq 2$. A
fact first observed by Arhangel’skiǐ and van Mill [AvM13] for $m=1$ and by
Hernández-Gutiérrez in the case $m\geq 2.$

######  Corollary 2.9 ([HG13]).

The space ${}^{m}\mathbb{A}$ is not countable dense homogeneous for any $m\geq
1.$

##  3 NON-HOMOGENEITY OF $\mathcal{F}_{m}(\mathbb{A})$

In this section we prove Theorem 1.3. It will be convenient to introduce some
notation. Let $\Delta_{m}=\\{x\in^{m}\mathbb{A}:\forall i\in m-1(x(i)\leq
x(i+1))\\}$, let $\rho:\Delta_{m}\to\mathcal{F}_{m}(\mathbb{A})$ be the map
given by $\rho(x)=\\{x(0),\dots,x(m-1)\\}$ and let $\sim$ denote the
equivalence relation on $\Delta_{m}$ defined by $x\sim y$ if and only if
$\rho(x)=\rho(y).$ Finally, let $q:\Delta_{m}\to\Delta_{m}/\sim$ be the
quotient map, we will sometimes write $[x]$, instead of $q(x),$ to represent
the equivalence class. We consider $\Delta_{m}/\sim$ as a topological space
with the quotient topology.

The following classical fact give us a more geometric representation of
$\mathcal{F}_{m}(\mathbb{A})$.

######  Proposition 3.1 ([Ga54]).

The map $\tilde{\rho}:\Delta_{m}/\sim\to\mathcal{F}_{m}(\mathbb{\mathbb{A}})$
given by $\tilde{\rho}([x])=\rho(x)$ is a homeomorphism.

The next proposition is straightforward and it is left to the reader.

######  Proposition 3.2.

Every clopen subset of ${}^{m}\mathbb{A}$ is homeomorphic to
${}^{m}\mathbb{A}$.

######  Lemma 3.3.

If $\mathcal{F}_{m}(\mathbb{A})$ is homogeneous, then it is homeomorphic to
${}^{m}\mathbb{A}$.

###### Proof.

Suppose $\mathcal{F}_{m}(\mathbb{A})$ is homogeneous, then there is an
autohomeomorphism $h:\Delta_{m}/\sim\to\Delta_{m}/\sim$ such that
$h([\overline{0}])=[x],$ where $x_{0}<x_{1}<\dots<x_{m-1}$. On one hand,
notice that, if $J_{0}<\dots<J_{m-1}$ is a sequence of pairwise disjoint
clopen intervals with $x_{i}\in J_{i}$ for $i\in m,$ then
$q\restriction\prod\limits_{i\in m}J_{i}:\prod\limits_{i\in
m}J_{i}\to\Delta_{m}/\sim$ is an homeomorphism. On the other hand, observe
that for any $0<\epsilon<1$ the clopen cube ${}^{m}[0,\epsilon[$ is a
saturated neighborhood of $\overline{0}$ such that
$q^{\prime\prime}(^{m}[0,\epsilon[)$ is homeomorphic to $\Delta_{m}/\sim.$
Since $h$ is continuous there is an $\epsilon>$ such that
$h^{\prime\prime}(^{m}[0,\epsilon[/\sim)\subset\prod\limits_{i\in m}J_{i}.$ It
follows, from the previous Lemma, that
${}^{m}\mathbb{A}\cong\prod\limits_{i\in m}J_{i}\cong
h^{\prime\prime}(^{m}[0,\epsilon[/\sim)\cong^{m}[0,\epsilon[/\sim\cong\Delta_{m}/\sim.$

∎

######  Theorem 3.4.

The hyperspace $\mathcal{F}_{m}(\mathbb{A})$ is not homogeneous for any $m\geq
2$.

###### Proof.

Suppose for a contradiction that there is a homeomorphism
$h:\Delta_{m}/\sim\to^{m}\mathbb{A},$ and let
$\Gamma=\\{[\overline{x}]\in\Delta_{m}/\sim:x\in\mathbb{A}\\}.$ Observe that
$\Gamma$ is homeomorphic to $\mathbb{A}$ and it is not $G_{\delta}$ in
$\Delta_{m}/\sim$ as
$q^{-1}(\Gamma)=\\{(x,\dots,x)\in^{m}\mathbb{A}:x\in\mathbb{A\\}}$ is not a
$G_{\delta}$ in $\Delta_{m}$ (by Lemma 2.5). We now consider the embedding
$\alpha:\mathbb{A}\to^{m}\mathbb{A}$ given by $\alpha(x)=h([\overline{x}])$.
Since $h^{\prime\prime}[\Gamma]$ is not a $G_{\delta}$ in ${}^{m}\mathbb{A},$
it follows, again by Lemma 2.5, that there exits $j_{0}\neq j_{1}\in m$ and a
clopen interval $J$ such that $\alpha_{i_{0}}:=\pi_{i_{0}}\circ\alpha$ and
$\alpha_{i_{1}}:=\pi_{i_{1}}\circ\alpha$ are strictly monotone restricted to
$J$. We will assume that both $\alpha_{i_{0}}\restriction
J,\alpha_{i_{1}}\restriction J$ are strictly increasing, as the other cases
are analogous.

######  Claim 3.5.

There is a countable subset $C\subset\pi^{\prime\prime}[J]$ such that
$\pi(\alpha_{i_{0}}(\langle a,0\rangle))=\pi(\alpha_{i_{0}}(\langle
a,1\rangle))$ and $\pi(\alpha_{i_{1}}(\langle
a,0\rangle))=\pi(\alpha_{i_{1}}(\langle a,1\rangle))$ for any
$a\in\pi^{\prime\prime}[J]\setminus C.$

###### Proof.

Let $C_{k}=\\{a\in\pi^{\prime\prime}[J]:\alpha_{i_{k}}(\langle
a,0\rangle)<\pi(\alpha_{i_{0}}(\langle a,1\rangle)]\\}$ for $k\in 2$. For each
$a\in C_{k},$ pick a rational $q_{a}$ such that $\alpha_{i_{k}}(\langle
a,0\rangle)<q_{a}<\pi(\alpha_{i_{0}}(\langle a,1\rangle)$. Observe that since
$\alpha_{i_{k}}$ is strictly monotone, the map $f:C_{k}\to\mathbb{Q}$ given by
$f(a)=q_{a},$ is one-to-one. Thus, $C=C_{0}\cup C_{1}$ is countable as
desired. ∎

For each $a\in A:=\pi^{\prime\prime}[J]\setminus C.$ Let
$P_{a}^{-}=\alpha(\langle a,0\rangle),Q_{a}^{+}=\alpha(\langle a,1\rangle)$
and let

$P_{a}^{+}=\alpha(\langle
a,0\rangle)\restriction_{(m-\\{i_{0}\\})}\cup(i_{0},\langle\pi(\alpha_{i_{0}}(\langle
a,0\rangle),1\rangle)$

and

$Q_{a}^{-}=\alpha(\langle
a,1\rangle)\restriction_{(m-\\{i_{1}\\}}\cup(i_{1},\langle\pi(\alpha_{i_{1}}(\langle
a,0\rangle),1\rangle).$

Pick an element $[x_{a}]$ belonging to

$h^{-1}(\\{P^{-}_{a},P^{+}_{a},Q^{-}_{a},Q^{+}_{a}\\})\setminus\\{\\{\tilde{\rho}^{-1}(\langle
a,0\rangle\\}),\tilde{\rho}^{-1}(\\{\langle
a,1\rangle\\}),\tilde{\rho}^{-1}(\\{\langle a,0\rangle,\langle
a,1\rangle\\})\\}.$

Observe that, by our choice of $x_{a},$ for any $x\sim x_{a}$ there is a $j\in
m$ so that $\pi(x(j))\neq a.$ By successively refining $A$, we can find an
uncountable subset $B\subset A,$ a natural number $N$ so that
$q^{-1}([x_{a}])=\\{x^{i}_{a}:i\in N\\},$ an $N$-tuple
$(j_{0},\dots,j_{N-1})\in m^{N}$, a rational number $q\in\mathbb{Q}$ such that
$x_{a}^{i}(j_{i})=x_{a}^{i^{\prime}}(j_{i^{\prime}})$ for all $i,i^{\prime}\in
N$ and $q\in]\pi(x^{i}_{a}(j_{i})),a[$ 333We are using the convention that
$]a,b[=]\min(a,b),\max(a,b)[.$ and $h([x_{a}])=P^{+}_{a}$ (the case
$h([x_{a}])=Q^{-}_{a}$ is analogous), for any $a\in B.$ Consider the clopen
cubes $U:=^{m}[\langle q,1\rangle,\langle 1,0\rangle]$ and $V:=^{m}[\langle
0,1\rangle,\langle q,0\rangle]$. Since both cubes are saturated we have that
$\tilde{U}:=q^{\prime\prime}[U]$ and $\tilde{V}:=q^{\prime\prime}[V]$ form a
clopen partition of $\Delta_{m}/\sim.$ Observe that $X:=\\{[\overline{\langle
a,0\rangle}]:a\in B\\}\subset\tilde{U}$ and $Y:=\\{[x_{a}]:a\in
B\\}\subset\tilde{V}$, since $B$ is infinite (uncountable) and
$\Delta_{m}/\sim$ is compact, it follows that its accumulation points are non-
empty and disjoint. However, this contradicts the fact that
$h^{\prime\prime}[X]=\\{P_{a}^{-}:a\in B\\}$ and
$h^{\prime\prime}[Y]=\\{P_{a}^{+}:a\in B\\}$ have the same set of accumulation
points. This finishes the proof of the Theorem.

∎

It would be interesting to see if the above theorem can be extended to the
hyperspace of all non-empty finite subsets $\mathcal{F}(\mathbb{A})$.

######  Question 3.6.

Is the hyperspace $\mathcal{F}(\mathbb{A})$ homogeneous?

##  4 HOMOGENEITY OF $\mathcal{F}_{2}(\mathbb{S})$.

In this section we prove Theorem 1.4. It is worth mentioning that our proof is
based on work of Bennett, Burke and Lutzer [BBL12] and we will also borrow
some of its notation.

First of all, since the Sorgenfrey line is homeomorphic to $[0,1[$ with the
subspace topology, we will assume that the $\mathbb{S}=[0,1[$. A Sorgenfrey
rectangle denote any set of the form $[a,b[\times[c,d[$ where
$a,b,c,d\in[0,1[$; $a<b$ and $c<d$. By the Euclidean closure of such a
rectangle we mean its closure in the euclidean topology of $[0,1[^{2}$. Let
$\Delta_{2}=\\{(x,y)\in\mathbb{S}^{2}:x\leq y\\}$ and let $\Delta$ be the
diagonal of $\mathbb{S}$.

For each $k\geq 1,$ let $L_{k}$ be the straight line joining the points
$(0,\frac{1}{k})$ and $(1,1)$.

######  Proposition 4.1 ([BBL12]).

There is a countable collection $\mathcal{T}$ of pairwise disjoint Sorgenfrey
rectangles such that:

  * (1)

$\bigcup\mathcal{T}=\Delta_{2}\setminus\Delta$;

  * (2)

for each $T\in\mathcal{T}$, the Euclidean closure of $T$ is disjoint from
$\Delta$;

  * (3)

for each $x\in[0,1[$ the set
$\\{T\in\mathcal{T}:T\cap(\\{x\\}\times]x,1[)\neq\emptyset\\}$ is infinite and
can be indexed as $\\{T_{m}:m\geq 1\\}$ in such a way that for all $k$ points
of $T_{k}$ lie above points of $T_{k+1}$.

  * (4)

for each $T\in\mathcal{T}$, there is a $k\geq 1$ such that $T$ is between
$L_{k}$ and $L_{k+2}.$

It worth pointing out that clause (4) is a consequence of the proof in
[BBL12].

Let $T$ be an element of the partition $\mathcal{T}$. If $T=[a,b[\times[c,d[$,
then define $T^{U}=[a,b[\times[\frac{c+d}{2},d[$,
$T^{L}=[a,b[\times[c,\frac{c+d}{2}[$ and $T^{S}=[c,d[\times[a,b[$. Finally,
let $\mathcal{T}^{S}=\\{T^{S}:T\in\mathcal{T}\\}.$

######  Remark 4.2.

Note that $T^{U}$ is the upper half of $T$, $T^{L}$ is the lower half of $T$
and $T^{S}$ is the reflection of $T$ across the diagonal $\Delta$.

######  Theorem 4.3.

The spaces $\Delta_{2}$ and $\mathbb{S}^{2}$ are homeomorphic.

###### Proof.

We shall define a homeomorphism $h:\Delta_{2}\rightarrow\mathbb{S}^{2}$.
First, we will define the function $h$. After that we will prove that $h$ is
1-1 and onto. Finally, we will prove that $h$ and its inverse are continuous.

###

For each $T=[a,b[\times[c,d[\in\mathcal{T},$ we consider the following
homeomomorphisms

$h_{T^{U},T^{S}}:T^{U}\to T^{S}\ {\rm and}\ h_{T^{L},T}:T^{L}\to T$

given by $h_{T^{U},T^{S}}(x,y)=(2y-d,x)$ and $h_{T^{L},T}(x,y)=(x,2y-c),$
respectively. Let

$h:=Id_{\Delta}\cup\bigcup\limits_{T\in\mathcal{T}}\left(h_{T^{L},T}\cup
h_{T^{U},T^{S}}\right),$

where $Id_{\Delta}$ represents the identity function restricted to the
diagonal. Since
$\Delta_{2}=\Delta\sqcup\bigsqcup\limits_{T\in\mathcal{T}}(T^{U}\sqcup T^{L})$
and $\mathbb{S}^{2}=\Delta\sqcup\bigsqcup\limits_{T\in\mathcal{T}}(T\sqcup
T^{S}),$ it follows that $h:\Delta_{2}\to\mathbb{S}^{2}$ is a bijection.
Notice that $h\restriction(\Delta_{2}\setminus\Delta)$ and
$h^{-1}\restriction(\mathbb{S}^{2}\setminus\Delta)$ are continuous, as
$h_{T^{U},T^{S}}$ and $h_{T^{L},T}$ are homeomorphism between clopen
subspaces.

We will now show that $h\restriction\Delta$ is continuous. Let
$(x,x)\in\Delta$ and $(x_{n},y_{n})(n\in\omega)$ be a sequence that converges
to $(x,x)$. We may assume, without lose of generality, that $x_{n}>x,y_{n}>x$
for any $n\in\omega$. Separately, consider three subsequences, namely, those
on the diagonal, those in the sets of the form $T^{U}$ and those in the sets
of the form $T^{L}$. Let $A_{0},A_{1},A_{2}$ denote the indexes of the
subsequences. If there are infinitely many points of the first type, then
their images converges to $(x,x)$ since $h$ is the identity at such points.

If there are infinitely many points of the second type, then their images have
the form $(2y_{n}-d_{n},x_{n}),$ where
$T_{n}=[a_{n},b_{n}[\times[c_{n},d_{n}[$ is the element of $\mathcal{T}$ that
contain $(x_{n},y_{n})$. Since $y_{n}$ converges to $x$ and
$x<2y_{n}-d_{n}<y_{n}$, we have that $\lim\limits_{n\in
A_{1}}h(x_{n},y_{n})=\lim\limits_{n\in A_{1}}(2y_{n}-d_{n},x_{n})=(x,x)$.

If there are infinitely many points of the third type, then their images have
the form $(x_{n},2y_{n}-c_{n}),$ where
$T_{n}=[a_{n},b_{n}[\times[c_{n},d_{n}[$ is the element of $\mathcal{T}$ that
contains $(x_{n},y_{n})$. Since $2y_{n}-c_{n}<d_{n}$, it is sufficient to
prove that:

######  Claim 4.4.

If $\lim\limits_{n\in A_{2}}(x_{n},y_{n})=(x,x)$, then $\lim\limits_{n\in
A_{2}}(x_{n},d_{n})=(x,x)$.

###### Proof.

Let $V=[x,x+\epsilon[^{2}\cap\Delta_{2}$ be a given open neighborhood of
$(x,x)$. Fix $k$ such that $\frac{1}{k}<\frac{\epsilon}{2}$. Since
$(x_{n},y_{n})$ converges to $(x,x)$, we can find $N$ so that
$(x_{n},y_{n})\in[x,x+\frac{\epsilon}{2}[^{2}$ and it is below the line
$L_{k+2}$ for all $n\geq N$ . We are left to show that $(x_{n},d_{n})\in V$
for all $n\geq N$. Let $n\geq N$ be given. Since $(x_{n},y_{n})$ is below the
line $L_{k+2}$ and every rectangle $T\in\mathcal{T}$ is between two lines
$L_{\ell}$ and $L_{\ell+2}$ for some $\ell.$ It follows that
$T_{n}=[a_{n},b_{n}[\times[c_{n},d_{n}[$ is below $L_{k}$. Hence,
$d_{n}-c_{n}<\frac{1}{k}<\frac{\epsilon}{2}$ and
$x<y_{n}<x+\frac{\epsilon}{2}$. Therefore, $(x_{n},d_{n})\in V$ as required. ∎

We are left to show that the inverse $h^{-1}$ is continuous on the diagonal.
Let $(x,x)\in\Delta$ be given and let $(x_{n},y_{n})(n\in\omega)$ be a
sequence that converges to $(x,x)$. We may assume, without lose of generality,
that $x<x_{n},y<y_{n}$ for any $n\in\omega$. Separately, consider three
subsequences, namely, those on the diagonal, those elements above the diagonal
and those in the sets below the diagonal. Let $A_{0},A_{1},A_{2}$ denote the
indexes of the subsequences. If there are infinitely many points of the first
type, then their images converges to $(x,x)$ since $h^{-1}$ is the identity at
such points.

If there are infinitely many points of the second type, then their images have
the form $(x_{n},\frac{y_{n}+c_{n}}{2})$ where
$T_{n}=[a_{n},b_{n}[\times[c_{n},d_{n}[$ are the elements of $\mathcal{T}$
that contains $(x_{n},y_{n})$. Since $y_{n}$ converges to $x$ and
$x<\frac{y_{n}+c_{n}}{2}<y_{n}$, we have that $\lim\limits_{n\in
A_{1}}(x_{n},\frac{y_{n}+c_{n}}{2})=(x,x)$.

If there are infinitely many points of the third type, then their images have
the form $(y_{n},\frac{x_{n}+d_{n}}{2})$ where
$T^{S}_{n}=[c_{n},d_{n}[\times[a_{n},b_{n}[$ are the elements of $\mathcal{T}$
such that $T_{n}^{S}$ contains $(x_{n},y_{n})$. Since
$x<\frac{x_{n}+d_{n}}{2}<d_{n}$, it is sufficient to prove that:

######  Claim 4.5.

If $\lim\limits_{n\in A_{2}}(x_{n},y_{n})=(x,x)$, then $\lim\limits_{n\in
A_{2}}(y_{n},d_{n})=(x,x)$.

###### Proof.

Let $V=[x,x+\epsilon[^{2}$ be a given open neighborhood of $(x,x)$. Let
$\tilde{L}_{k}$ denote the line from $(\frac{1}{k},0)$ to $(1,1)$ for $k\geq
1$. Fix $k$ such that $\frac{1}{k}<\frac{\epsilon}{2}$. Since $(x_{n},y_{n})$
converges to $(x,x)$, we can find $N$ so that
$(x_{n},y_{n})\in[x,x+\frac{\epsilon}{2}[^{2}$ and it is above the line
$\tilde{L}_{k+2}$ for all $n\geq N$ . We are left to show that
$(y_{n},d_{n})\in V$ for all $n\geq N$. Let $n\geq N$ be given. Since
$(x_{n},y_{n})$ is above the line $\tilde{L}_{k+2}$ and every rectangle
$T\in\mathcal{T}^{S}$ is between two lines $\tilde{L}_{\ell}$ and
$\tilde{L}_{\ell+2}$ for some $\ell.$ It follows that
$T^{S}_{n}=[c_{n},d_{n}[\times[a_{n},b_{n}[$ is above $\tilde{L}_{k}$. Hence,
$d_{n}-c_{n}<\frac{1}{k}<\frac{\epsilon}{2}$ and
$x<x_{n}<x+\frac{\epsilon}{2}$. Therefore, $(y_{n},d_{n})\in V$ as required. ∎

This concludes the proof of the Theorem. ∎ As a corollary we obtain.

######  Corollary 4.6.

$\mathcal{F}_{2}(\mathbb{S})$ is homogeneous.

###### Proof.

By Proposition 4.1, $\mathcal{F}_{2}(\mathbb{S})$ is homeomorphic to
$\Delta_{2}$. Since $\mathbb{S}^{2}$ is homogeneous and $\Delta_{2}$ is
homeomorphic to it, by the previous theorem, the result holds. ∎

## References

  * [Ar87] Arkhangel’skiǐ, A. V. _Topological homogeneity. Topological groups and their continuous images_. (Russian) Uspekhi Mat. Nauk 42 (1987), no. 2(254), 69–-105, 287.
  * [AvM13] Arhangel’skiǐ, A. V.; van Mill, J. _On the cardinality of countable dense homogeneous spaces_. Proc. Amer. Math. Soc. 141 (2013), no. 11, 4031–-4038.
  * [BBL12] Bennett, Harold; Burke, Dennis; Lutzer, David _Some questions of Arhangel’skiǐ on rotoids_. Fund. Math. 216 (2012), no. 2, 147–-161.
  * [En89] Engelking, Ryszard _General topology_. Translated from the Polish by the author. Second edition. Sigma Series in Pure Mathematics, 6. Heldermann Verlag, Berlin, 1989. viii+529 pp. ISBN: 3-88538-006-4
  * [HG13] Hernández-Gutiérrez, Rodrigo. _Countable dense homogeneity and the double arrow space_. Topology Appl. 160 (2013), no. 10, 1123–-1128.
  * [Ga54] Ganea, Tudor _Symmetrische Potenzen topologischer Räume._ (German) Math. Nachr. 11 (1954), 305–316.
  * [SW75] Schori, R. M.; West, J. E. _The hyperspace of the closed unit interval is a Hilbert cube._ Trans. Amer. Math. Soc. 213 (1975), 217–235.
  * [Sce76] Ščepin, E. V. _Topology of limit spaces with uncountable inverse spectra. (Russian)_ Uspehi Mat. Nauk 31 (1976), no. 5 (191), 191–226.

Sebastián Barría
Email<EMAIL_ADDRESS>

Carlos A. Martínez-Ranero
Email<EMAIL_ADDRESS>
Homepage: www2.udec.cl/ cmartinezr

Same Address:
Universidad de Concepción, Concepción, Chile
Facultad de Ciencias Físicas y Matemáticas
Departamento de Matemática