# Microgrid - The microthreaded many-core architecture

Irfan Uddin
University of Amsterdam, The Netherlands
<EMAIL_ADDRESS>
###### Abstract

Traditional processors use the _von Neumann_ execution model, some other
processors in the past have used the _dataflow_ execution model. A combination
of _von Neuman_ model and _dataflow_ model is also tried in the past and the
resultant model is referred as _hybrid dataflow_ execution model. We describe
a hybrid dataflow model known as the microthreading. It provides constructs
for creation, synchronization and communication between threads in an
intermediate language. The microthreading model is an abstract programming and
machine model for many-core architecture. A particular instance of this model
is named as the microthreaded architecture or the Microgrid. This architecture
implements all the concurrency constructs of the microthreading model in the
hardware with the management of these constructs in the hardware.

###### Contents

  1. 1 Introduction
  2. 2 Latency tolerance
  3. 3 The microthreading model
  4. 4 The Microgrid
  5. 5 Programming the Microgrid
  6. 6 The microthreading model in the context of the Microgrid
  7. 7 I/O in the Microgrid
  8. 8 Conclusion

##  1 Introduction

Traditional processors are based on the _von Neumann_ execution model. In this
model a sequence of instructions is executed one-by-one and the state of the
program is identified by a single program counter. However, performance can
not be improved by executing instructions sequentially. In order to improve
the performance, _dataflow_ scheduling is used where instructions are executed
based on the availability of data. Theoretically, dataflow models are parallel
execution models, because instructions can be scheduled only with the
availability of the data, and the scheduled instructions can be executed
independently. Most of the out-of-order execution techniques are derived from
dataflow scheduling. However, the execution of the program is still determined
largely by the instruction sequence as dataflow scheduling is only applied to
a few instructions in a small window over the sequential code. In contrast,
Moonsoon [29] and Wavescalar [40] are based on dataflow models.

The _von Neumann_ model is simple but sequential, the _dataflow_ model is
parallel and improves the efficiency of the execution of the program but with
the cost of adding complexity in the hardware design, therefore a _hybrid
dataflow_ model [6, 17] was tried to combine the advantages of both. The issue
with generalized dataflow model is the requirement of a matching store to
detect which operations become ready to execute when its dependencies are
satisfied. The efficient organization of the matching store is not so clear to
the designers of the execution models. With a hybrid dataflow model, the
ordering of instructions can be sequentialized to reduce the need for a big
matching store. In hybrid dataflow models instructions are executed based on
the _von Neumann_ model within a thread but there is support for dynamic
execution of threads based on the _dataflow_ model. This model allowed
multicore architectures to exploit parallelism in programs. P-RISC [33],
Multiscalar [38] and DDM-CMP [39] are based on the _hybrid dataflow_ model.

Modern many-core systems one way or other provide concurrency constructs to
exploit parallelism. To quote Prof. Chris Jesshope _By 2020 we could see up to
$10^{4}$ cores and $10^{6}$ hardware threads on a single chip_. The
concurrency constructs introduced by the microthreading model are implemented
in the instruction set of the microthreaded architecture which is also
referred as the Microgrid. This architecture assumes a lot of concurrency in
the applications and provides the concurrent architecture to exploit
parallelism.

The rest of the paper is organized as follows. In Section 2 we define the
latency tolerance feature in computer architecture. We explain the details of
the microthreading model in Section 3 and the details of the architecture
based on this model in Section 4. We describe the programming of the Microgrid
in Section 5. We explain the microthreading model in the context of the
Microgrid in Section 6. We present the I/O in the Microgrid in Section 7 and
conclude the paper in Section 8.

##  2 Latency tolerance

In any program, a computation is preceded and followed by memory operation
which takes a variable amount of time as it depends on the locality of the
data i.e. the data is located in L1-, L2-,L3- caches or off-chip memory. In
single-threaded programs the processor has to wait for memory operations to
complete and then continue with the computation. In multi-threaded programs,
when a memory operation is issued, the thread may be suspended and execution
is switched to another available thread. Because of dataflow scheduling, the
memory operation completes asynchronously and wakes up the suspended thread.
The execution of program is tolerant to the long latency operations and is
shown in fig. 1 assuming multiple instructions issued and executed in a single
core.

The use of multiple threads per core in order to hide latency has been
understood for long time [53]. For instance, software time sharing is adequate
to tolerate external I/O latencies but can not tolerate other long latency
operations (e.g. memory access) because of the absence of fine-grained latency
tolerance. Hardware multi-threading with dynamic scheduling is used to
tolerate long latency operations e.g. MTA cores can switch on every miss
operation but it requires a long pipeline flush. Niagara cores switch on the
issue of a memory operation [37] and therefore tolerate long latency
operations, but can not tolerate the latency in FPUs or other asynchronous
operations (e.g. management of threads).

Figure 1: Latency tolerance in multi-threaded programs assuming multiple
instructions issued and executed in the core.

##  3 The microthreading model

The microthreading model [18] is based on a type of _hybrid dataflow_ model
and has evolved from DRISC [4] (Dynamically-scheduled RISC) which was proposed
in 1996 with the goal of separating computation from communication. DRISC
provides dataflow scheduling in RISC core, which executes instructions
asynchronously and with multiple threads it can tolerate the latency of long
latency operations. The innovation in this model is that instead of multiple
threads, an ordered set of threads referred as families are used, which
provide composability in programs. The operations to create families resemble
the fork/join operations found in most parallel programming models. The
microthreading model is actually a hybrid of von Neumann model, dataflow
scheduling of threads.

The microthreading model has been refined over the decade from a single
processor model to an abstract machine model for many-cores and can capture as
much concurrency as possible using families of threads in a dynamically
evolving concurrency tree. A family is comparable to loop or function call in
traditional programming. Any thread can create further families (any
heterogeneous combination is supported by the model) showing a hierarchy of
threads. An example concurrency tree of the microthreading model is shown in
fig. 2, where every family is composed of some number of threads and every
thread can create another family.

Figure 2: An example concurrency tree created by the microthreading model. A
family can create any combination of threads and the hierarchy of families can
go until any level.

As the overhead of creating and synchronizing threads in software is 10 to 100
thousands cycles on contemporary hardware [49]. The microthreading model
shifts the perspective from software threads to hardware threads with
concurrency management in hardware in order to reduce the cost from few
thousands cycles to just a few cycles. The number of cycles taken by an
instruction depends on the dynamic state of the architecture, but because of
asynchronous completion and fine-grained latency tolerance the model has the
potential to achieve the goal of RISC i.e. _one cycle per instruction_. In the
microthreading model the throughput of the program can potentially demonstrate
that every instruction takes one cycle to complete, assuming single
instruction issued and executed in the core.

###  3.1 Communication and synchronization

The microthreading model supports hybrid dataflow scheduling by using
I-structures [3]. An I-structure is a data structure with the semantics of
dataflow i.e. every element has a state of either _full_ or _empty_. Any
operation accessing an element with _empty_ state is suspended. The state of
the element is changed to _full_ asynchronously, and the suspended operation
is released to access the element. This process is termed as _split-phase_
operation [54] which has two phases; requesting and consuming. A request to
the desired data is issued, but if the data is not available, the request is
suspended. The execution model can continue executing other computations while
the request is in the progress. When the data arrives, the suspended operation
is released and the instruction can consume the data.

The microthreading model uses I-structure as a set of channels; globals and
shared to support communication between threads. These channels are actually
registers address using the register names of the underlying ISA. But for the
sake of generality these registers are referred as channels. These channels
have blocking read and non-blocking writes. By blocking we mean that the
operation is suspended because of the unavailability of the data, and by non-
blocking we mean that the operation is performed and the writing of the data
complete asynchronously. Global channels are mapped to all threads in the
family and have read only access. Shared channels provide the mechanism for
the communication only between adjacent threads uni-directionally in the
ordered sequence of threads in the family. The sharing of synchronizers
between threads enables fast thread-to-thread synchronization, for example to
implement dependencies in a loop. The creating thread communicate with the
created threads using messages, which can access the synchronizing memory of a
family remotely. The one-way communication is restricted but ensures a
deadlock free communication [52]. The communication and synchronization
between threads are shown in fig. 3 and more details can be found in [21, Sec.
4.3.3.3].

Figure 3: The communication between threads and the synchronization of the
family.

###  3.2 Memory consistency model

The microthreading model addresses consistency using two models for threads
and families. A single thread is sequentially consistent, as all the
instructions within a thread appear to execute in sequential order. A family
is weakly consistent, as it follows the three properties of Weak Consistency:

  * •

Any created thread can perform a read or write operation only after all the
writes by the creating thread prior to the creation of the family.

  * •

The family can be synchronized only when all previous write operations by the
created threads are performed.

  * •

The creating thread can perform a read or write operation only after the
created family is synchronized.

Memory consistency models [11, 28] have been defined for different programming
and machine models. We present only two consistency models which are relevant
to the microthreading model.

  * •

Sequential Consistency (SC) :

A system is sequentially consistent if the result of the execution of
instructions is the same as if instruction of all the cores were executed in
some sequential order. In addition, the instructions of each individual core
appear in the same sequence as specified by the program. SC has two cases:

    1. 1.

A read operation by any processor/thread is allowed to perform only if all
previous read and write accesses are performed globally.

    2. 2.

A write operation by any processor/thread is allowed to perform only if all
previous read and write accesses are performed globally.

  * •

Weak Consistency (WC) :

A system is weakly consistent if the synchronizing operation is performed only
if there is no pending ordinary (non-synchronizing) read or write operations,
and any ordinary read or write operations can not be performed if there is a
pending synchronizing operation. The weak consistency is defined in [11] but
we are slightly modifying the terminology to match with the microthreading
model. WC has three cases:

    1. 1.

All previous synchronizing operations must be performed before an ordinary
operation is performed.

    2. 2.

All previous ordinary operations must be performed before the synchronizing
variable.

    3. 3.

Synchronizing operations are sequentially consistent with respect to one
another.

###  3.3 The notion of resources in the microthreading model

The microthreading model is an abstract machine and programming model and
therefore does not have physical resources, but it is designed with the notion
of resources as the model addresses many-core architectures. A family of
threads is allocated to a group of resources and are referred as _place_.
These resources can be one or more cores, single or many threads etc. A family
created on a _place_ will execute there until synchronized and a thread
allocated to a core will execute there until terminated.

In order to control the number of threads on a core per family, _windowsize_
is introduced as a run-time parameter. A programmer can carefully use this
parameter to use only the requested number of resources, leaving resources for
other families (or may be more important families). More importantly this
parameter is used to avoid deadlock from dependencies down the concurrency
tree. It can wisely be used by the programmer or compiler to ensure that at
least one leaf of the concurrency tree can continue execution by using the
available resources and hence avoid deadlocks. The _windowsize_ limits the
number of threads executing in a family, similar to the concept as k-bounded
loops [8] in dataflow scheduling. The parameter ’k’ is comparable to the
_windowsize_ in the microthreading model. However, it should be noted that
_windowsize_ is per core and ’k’ is per loop which may be distributed on many
cores.

The microthreading model introduces _break_ used by a thread to terminate the
execution of the family. The _break_ will let the already created threads of
the family to complete and will stop the creation of any new threads in the
family. It is comparable to the _exit_ statement in loops or functions in
traditional programming, and is useful when the synchronization of the family
depends on some dynamic conditions.

###  3.4 Concurrency constructs

The microthreading model defines concurrency constructs to use the concurrency
provided by the hardware. But these constructs need to be introduced in some
intermediate language in order to write programs. In this section we explain
some of the concurrency constructs of the microthreading model and show that
these constructs are defined in an intermediate language referred as SL [21,
22]. In Section 5 we will show an example program that will demonstrate the
use of concurrency constructs of the microthreading model in an application.

### Allocation and deallocation of place

A group of cores i.e. _place_ is required to be allocated before the creation
of a family and released when the family is synchronized.

  * •

$sep\\_alloc(<parameters>)$ and $sep\\_free(<parameters>)$
are used to allocate and de-allocate cores through a software API. The
$<parameters>$ are a list of parameters passed for allocation and de-
allocation e.g. specifying the strategy of allocation or number of cores etc.
and can be found in [19].

### Creation and synchronization of family

A family of threads can be created by using $sl\\_create$ constructs similar
to a loop in traditional programming. The created family can be synchronized
using $sl\\_sync$ construct.

  * •

$sl\\_create(fid,pid,start,limit,step,windowsize,options,thread[,<arguments>])$
defines the creation of a parameterized family.

  * •

$fid$
is the identifier of the family of type $sl\\_family\\_t$.

  * •

$pid$
is the identifier of the _place_ of type $sl\\_place\\_t$.

  * •

$start$, $limit$ and $step$
indicate the starting, ending and iteration step counter of threads (similar
to the iterators in a loop).

  * •

$windowsize$
determines the upper limit on the number of threads that can be created on a
core.

  * •

$option$
decides the way the family should be created an executed. e.g. $sl\\_forceseq$
will force the family to execute sequentially.

  * •

$thread$
is the name of the thread which defines the code to be executed by created
threads in the family.

  * •

$<argument>$
is a comma separated list of global and shared arguments passed to the thread.

  * •

$sl\\_sync()$
is used for the synchronization of the family.

### Global and shared channels

The global and shared channels introduced by the microthreading model are
implemented as global and shared variable in the intermediate language. They
are used as parameters/arguments to the creation of a family of thread.

  * •

$sl\\_glarg(type,variable,value)$ and $sl\\_sharg(type,variable,value)$
indicates the global and shared $variable$ of $type$ with some $value$ passed
from the creating thread to the created thread.

  * •

$sl\\_glparm(type,variable)$ and $sl\\_shparm(type,variable)$
defines the global and shared $variable$ of $type$ received by the created
thread from the creating thread.

  * •

$sl\\_getp(variable)$
is used to read from global or shared $variable$.

  * •

$sl\\_setp(variable,value)$
is used to write the shared $variable$ with a modified $value$ to be read by
the next thread.

  * •

$sl\\_seta(variable,value)$
is used by the creating thread to write a $value$ to the shared variable to
the first thread of the family.

  * •

$sl\\_geta(variable)$
is used by the creating thread to read the shared $variable$ from the last
thread in the family.

### Starting and terminating threads

Threads are implicitly created with the creation of a parameterized family and
terminated when all of their instructions are executed. But programmers need
to define the starting and terminating of a thread similar to the way
functions are defined in traditional programming.

  * •

$sl\\_def(type,<parameter>)$
is used to define a thread with return of $type$ and $<parameter>$ of a list
of the global or shared variables used by the thread.

  * •

$sl\\_enddef$
defines the terminating of the thread.

  * •

$sl\\_index(index)$
can be used to retrieve the $index$ of the ordered set of threads in the
family.

### Breaking family

Any thread in a family can use the break statement to stop creation of new
threads in the family. The syntax is given below:.

  * •

$sl\\_break$
is used to stop creating new threads in the family.

###  3.5 More about families

The microthreading model has evolved over the years and have introduced
different types of families as per the requirements of the programs. All the
families are created using $sl\\_create$ construct (except detached family,
see below). The family can be of any of the type (described in this section)
based on the way the created threads are executing. However, some types of
families are need to be explicitly defined by passing a parameter to the
create construct. In this section we give a brief overview of the different
types of families supported by the microthreading model with the aim that
programmers can write a parallel program using different combination of
threads and families. Families that are required to be explicitly defined at
the time of creation are explicitly stated in their respective subsection.

#### Independent family

A family is called independent family when its created threads do not require
any communication between threads. Embarrassingly parallel applications
generally do not require communication between created threads and the
microthreading model supports these types of applications by creating them as
independent families.

#### Dependent family

Threads in dependent family communicate with each other. Fine-grained parallel
applications require a lot of communication and coarse-grained parallel
applications communicate a little between threads. The microthreading model
supports these types of application by creating dependent families. These
families communicate with each other through shared channels introduced
earlier (c.f. Section 3.1). Dependent families are inherently sequential and
therefore do not get any speedup by distributing the threads on many cores.
But in the microthreading model these threads get benefit from latency
tolerance and asynchronous completion as a dependent family can be executed
along with other families.

#### Homogeneous family

All families are statically homogeneous but can be made dynamically
heterogeneous if the programmer calls/creates different functions in a thread
dependent on the index of the thread.

#### Heterogeneous family

A family can be composed of threads that are not identical to each other. The
programmer need to explicitly write the code for different threads based on
the index of the thread to perform different operations.

#### Detached family

A family is required to be synchronized before continuing further. But there
may be situations when a family may not want to synchronize and is called
_detached_ family. For instance, creating a family that prints some characters
on terminal may not require synchronization as all the created threads perform
only read operations and do not modify any memory. The programmer has to
explicitly specify the _detached_ family by creating a family with
$sl\\_detach(<parameters>)$ instead of $sl\\_create(<parameters>)$, where
$parameters$ are defined in Section 3.

#### Exclusive family

To support mutual exclusion in the microthreading model, exclusive families
are introduced. Exclusive families are treated differently to regular families
because of the requirement of being mutually exclusive. More details about
mutual exclusion in the microthreading model can be found in [21, Sec. 14.1].
To create an exclusive family the programmer have to explicitly use
$sl\\_exclusive$ in the place of $options$ in the create construct. Generally
exclusive families consist of a single thread.

#### Sequentialized family

A family can be forced to execute sequentially, to avoid using resources by
creating many threads. The programmer has to explicitly use $sl\\_forceseq$ at
the place of $options$ in the create construct. The sequentialized family will
execute as regular code of the parent thread.

##  4 The Microgrid

Microgrid is actually a blueprint with parameters defined for the
architecture. There are many Microgrids; with 1 core, 128 cores, 1000 cores,
random bank memory, COMA etc. We use the term Microgrid to generalize all
instances of the blueprint. At some time we talk about a particular instance,
but then we explicitly give the details of the parameters. In the context of
the Microgrid, a core is explicitly termed as microthreaded core to
differentiate from traditional cores. In addition, a thread is termed as
microthread to distinguish it from traditional threads.

The basic component of the Microgrid is the microthreaded core, and it is
important that we understand the execution of instructions in the core in
order to simulate the core at the high-level. The concurrency constructs of
the microthreading model are implemented in the instruction set (ISA) of the
core. The cores are designed to be simple; single issue, in-order, 6-stage
pipeline [20] and based on RISC. Some components of the operating system are
implemented in the silicon of the core [7] e.g. scheduler, resource
allocation, mapping etc. Some energy inefficient features are removed from the
design of the core e.g. speculation, out-of-order execution and cache
prefetching.

Figure 4: The microthreaded core.

The 6 stage pipeline of the core is shown in fig. 4, where we are not showing
the scale of components, but mainly the layout of components. It is a classic
RISC core with some modifications to existing components and adding some more
components to support the concurrency constructs of the microthreading model
in the core. The instruction fetch (IF), instruction decode (ID), register
read (RR), execute (EX), memory (MEM), write back (WB), I-cache, D-cache,
Integer register file, Floating register file and shared FPU are existing
components but slightly modified in order to support the ISA of the Microgrid.
The scheduler, allocator, network, thread table and family table are the newly
added components to support the concurrency constructs of the microthreading
model. The thread table and family table are used to store the thread contexts
and family contexts. Every core also has a single exclusive context for
creating an exclusive family and thread. The shared channels in the
microthreading model are implemented in the registers of the cores. These
registers are synchronizing and provide two ports for synchronous and
asynchronous completion e.g. D-cache and FPU operations are completed
asynchronously and therefore connected to the asynchronous ports of the
registers. The bus interface connects the L1-cache to the snoopy bus and the
network interface connects the core to the network of other cores on the chip.

The threads in hardware are supported by the thread management unit through
the instruction set of the core for creation and synchronization of threads.
It has lowered the overhead of creation and synchronization of software
threads from more than ten thousands of cycles to just few cycles. It also has
extremely low overhead of context switching (zero cycle) and provides fine-
grained interleaving i.e. interleaving at every cycle. However, this
interleaving is not as strict as in traditional threads. Threads can execute
multiple instructions from a single thread until a context switch is required.
Interleaving can be bypassed to maximize pipeline usage if there is no other
available thread. In single-threaded programs interleaving does not make sense
anyway. To ensure fairness in the execution of threads, interleaving is
enforced so that no thread can monopolize the execution time of the core.

The binary code of a program generated for the microthreaded core can be
executed on any other core that supports the same instruction set as
Microgrid. The other core may not support concurrent execution and the code
will be executed as single threaded. The code can also be executed on
different number of thread slots per core. This is called binary code
compatibility i.e. the binary code may not get the same performance but at
least it will not fail, its performance will be gracefully degraded.

As Microgrid provides many cores on a single chip, we show a group of four
cores in fig. 5 to demonstrate the interconnection of large number of cores.
The delegation network is a Network-on-Chip (NoC) where all cores are
addressable from all other cores. Currently it is implemented as a fully
connected network in MGSim, but could be implemented as a mesh network in the
hardware implementation. A core is connected to the previous and the next core
by a distribution network. Two cores share an FPU, and every core has an
L1-cache which are connected to L2-cache by a snoopy bus. L2-caches are
connected with each other in the distributed cache network. In order to handle
deadlock in memory network, every L2-cache has an incoming and outgoing
message buffer. An example layout of the 128-core Microgrid in a single chip
is shown in fig. 6.

Figure 5: A group of four cores, each core has an L1-cache, two cores share an
FPU and four cores share an L2-cache. Figure 6: The layout of 128 cores on the
Microgrid chip.

###  4.1 The communication network

The Microgrid chip has two communication networks on the chip, in addition to
the distributed memory network.

#### Delegation network

Every core is connected to every other core by a bi-directional fully
connected network. This network is highly efficient because a message travels
in 10 or even less cycles from source to destination. The current
implementation of the Microgrid assumes a single cycle, node-to-node routing
in a lightly loaded network, but in a loaded network it may take more cycles
due to contention and buffering delays. Since delegation network is very
efficient, it is used only for the concurrency management between cores that
are not adjacent.

#### Distribution network

All the cores are connected in a single bi-directional daisy-chained network
in a Moore curve. The curve can be chosen in a way to preserve locality in
L1-caches and L2-caches. It takes two cycles to travel from one core to an
adjacent core. The cycles taken by a return trip of a message from a core to
any other core on the distribution network is given in Eq: 1, where $c$ is the
number of cores.

$delay=2\times 2\times c$ (1)

The distribution network is used for the logical partitioning of the chip i.e.
different parts of the program can be executed on different parts of the chip.
It provides grouping of cores to be used for delegating a family, where the
distribution network knows the starting core in the group and the size of the
group.

###  4.2 Resource management in the hardware of the Microgrid

An integer value in the source program is used to identify a group of adjacent
cores where a family can be delegated. We refer to the group of cores as
_place_ and the integer value that identify the place as _placeid_. The
identifier can identify the starting core of the place and the size of the
place. More details about places can be found in [24, 22] and [21, Chap. 11 &
App. E].

A family can execute on the same core as the parent thread or the same place
as the parent thread. The former is called _local_ place and the later is
called _default_ place and are identified by place id as $0$ and $1$
respectively. The execution of a family on a place different than used by the
parent thread is called _delegation_. We can perform some arithmetic
operations on _placeid_ to derive the starting core and the size in the place.
The starting core can be calculated as given in Eq: 2 and the size of the
place can be calculated as given in Eq: 3. The size of the place is always in
power of 2, and the starting core must have the _coreid_ which is multiple of
the size of the place. This is a restriction, but easy in implementation as
this information can be derived from integers.

$starting\\_core\;\;=\;\;(placeid\;\;\&\;\;(placeid\;-\;1))\;>>\;1$ (2)

$size\;\;=\;\;placeid\;\;\&\;\;-placeid$ (3)

###  4.3 Proposed software service to access resources in the Microgrid

A software layer for the allocation of resources is defined in a protocol
referred as SEP [19, 27] which provides an easy to implement and efficient
management of resources. In the initial research work, a single core on the
Microgrid is reserved for the operations of SEP. It works in mutually
exclusive manner, and can soon become a bottleneck when a lot of requests are
coming to this single core. Some research is ongoing in avoiding bottleneck
and making the management hierarchical.

SEP is implemented using the well-known binary buddy allocation [30] of the
memory management. An example of buddy allocation used for cores in the
Microgrid is shown in fig. 7. It shows a system having a total of eight cores
with their identifiers given on the top. The time the system is initialized,
all the cores are in one group. Then a request is issued to allocate one core
and involves these steps:

  * •

Divide 8 cores in half.

  * •

Still bigger than required, divide 4 cores into half.

  * •

Still bigger than required, divide 2 cores into half.

  * •

We found a single core as requested, allocate the single core.

A request for a given number of cores, will allocate the group of cores if
available. In case the available group is larger than requested, divide the
bigger group into smaller group until the group of requested cores is
obtained. When the allocated cores are released, they are grouped into a
larger group. In the given example when the last 4 cores are released it is
grouped into larger group of 8 cores, bringing the system to the initial
state.

Figure 7: An example of the binary buddy allocation of cores by SEP.

A programmer can choose different numbers of cores in a place. Every time a
place is requested, a group of cores which are not allocated to any other
family is allocated. The allocated cores can be used by the family (and sub
families if any) to which the place is allocated, and can not be allocated to
any other family until explicitly de-allocated. SEP provides two API to
programmers; $sep\\_alloc()$ and $sep\\_free()$ for allocation and de-
allocation respectively similar to $malloc$ and $free$ in C. The allocation
and de-allocation of SEP can be performed asynchronously, but in the current
implementation these processes are not asynchronous. The moment the allocation
or de-allocation is issued by a thread, the thread will wait until the
operation is completed. The allocation of place depends on the policy given
below:

  * •

Minimum: Allocate at least the number of cores specified (may be more if
available).

  * •

Maximum: Allocate at most the number of cores specified (may be less if
unavailable).

  * •

Exact: Allocate the exact number of cores. The allocation will fail if the
given number of cores can not be allocated.

  * •

Any size: Any available size in the power of 2 will be allocated, starting
from the lowest available size of the group.

##  5 Programming the Microgrid

In this section we show an example program i.e. Matrix Multiplication of equal
sized matrices, to demonstrate the way programs are written for the Microgrid.
The objective is to show that a sequential C program can be transformed to a
microthreaded program easily by high-level programming languages, a compiler
or with little effort by the programmer. We also show the concurrency
constructs in the generated assembly to demonstrate the way the concurrency
constructs are supported in the ISA of the Microgrid.

#### Sequential C program

The sequential C code for Matrix Multiplication of size $1000\times 1000$ is
shown in listing LABEL:code:seq_matmul. We allocate three arrays; two for
source matrices and one for the result matrix. Once the memory is allocated,
we can fill these arrays with some numbers, but for saving space in the page,
we assume the existing values present in those memory locations. To perform
matrix multiplication we write three loops; outer loop, middle loop and inner
loop. The inner loop is the one which multiplies the two elements of the
source matrices and stores in the result matrix. After the multiplication is
completed, we free the allocated memory.

Listing 1: Sequential execution of Matrix Multiplication.

⬇

#include <stdio.h>

int N = 1000;

int main()

{

// Allocate memory for matrices

int *A = (int*) malloc(N * N * sizeof(int));

int *B = (int*) malloc(N * N * sizeof(int));

int *C = (int*) malloc(N * N * sizeof(int));

int i, j, k;

// Perform the multiplication

// matmul_outer

for(i=0; i<N; i++)

{

// matmul_middle

for(j=0; j<N; j++)

{

//matmul_inner

for(k=0; k<N; k++)

{

C[i*N+j] += A[i*N+k] * B[k*N+j];

}

}

}

free(A), free(B), free(C);

return 0;

}

#### Microthreaded program

The microthreaded program for the Matrix Multiplication of size $1000\times
1000$ written in SL is shown in listing LABEL:code:par_matmul. In the
$t\\_main$ function, we first allocate a group of 8 cores in the Microgrid.
Then we allocate three arrays for source and result matrices. Then we replace
the outer loop by creating a family of $N$ threads. The threads in the outer
family create further middle families and then each of those creates the inner
family. The inner family perform the multiplication of elements in source
arrays and store the multiplication in the resultant array. The transformation
from sequential program to microthreaded program involves the creation of
families and shared and global parameters. Once all the families are
synchronized, the allocated memory to arrays and allocated cores are released.

Listing 2: The microthreaded version of Matrix Multiplication.

⬇

#include <svp/sep.h>

#include <stdio.h>

int N = 1000;

//matmul_inner

sl_def(matmul_inner, void,

sl_shparm(long, sum), sl_glparm(void*, A),

sl_glparm(void*, B), sl_glparm(size_t, i),

sl_glparm(size_t, j)) {

sl_index(k);

int (*A)[N][N] = (int (*)[N][N])(void*) sl_getp(A);

int (*B)[N][N] = (int (*)[N][N])(void*) sl_getp(B);

int v = (*A)[sl_getp(i)][k] * (*B)[k][sl_getp(j)];

sl_setp(sum, v + sl_getp(sum));

}sl_enddef

//matmul_middle

sl_def(matmul_middle, void,

sl_glparm(void*, A), sl_glparm(void*, B),

sl_glparm(void*, C), sl_glparm(size_t, i)) {

sl_index(j);

sl_create(,,0,N,,,,matmul_inner,

sl_sharg(long, sum, 0), sl_glarg(void*, , sl_getp(A)),

sl_glarg(void*, , sl_getp(B)), sl_glarg(size_t, , sl_getp(i)),

sl_glarg(size_t, , j));

sl_sync();

int (*C)[N][N] = (int (*)[N][N])(void*) sl_getp(C);

(*C)[sl_getp(i)][j] = sl_geta(sum);

}sl_enddef

//matmul_outer

sl_def(matmul_outer, void,

sl_glparm(void*, A), sl_glparm(void*, B),

sl_glparm(void*, C)) {

sl_index(i);

sl_create(,,0,N,,,,matmul_middle,

sl_glarg(void*, , sl_getp(A)), sl_glarg(void*, , sl_getp(B)),

sl_glarg(void*, , sl_getp(C)), sl_glarg(size_t, , i));

sl_sync();

}sl_enddef

sl_def(t_main, void) {

// Allocate a place using SEP

int core = 8;

sl_place_t pid;

if (sep_alloc(root_sep, &pid, SAL_EXACT, core) == -1) {

printf(”cannot␣allocate␣a␣place.”);

exit(1);

}

// Allocate memory for matrices

int *A = (int*) malloc(N * N * sizeof(int));

int *B = (int*) malloc(N * N * sizeof(int));

int *C = (int*) malloc(N * N * sizeof(int));

// Perform the multiplication

sl_create(,pid,0,N,,,,matmul_outer,

sl_glarg(void*, , A), sl_glarg(void*, , B), sl_glarg(void*, , C) );

sl_sync();

free(A); free(B); free(C); sep_free(root_sep, &pid);

} sl_enddef

#### Microthreaded assembly code

The microthreaded assembly code is shown in listing
LABEL:code:assembly_matmul. We can see the assembly instructions of
concurrency constructs i.e. $allocate$ for the allocation of family, $crei$
for creation of family, $sync$ for synchronization of family, $puts$ writing a
shared variable, $gets$ reading from a shared variable etc. This is the
innovation in the Microgrid, which avoids the mapping of software threads to
hardware threads, which reduces the overhead from more than 10-100 thousands
cycles of software threads to just few cycles in hardware threads. The ISA of
program is scheduled by the microthreaded core with the hardware support for
concurrency management.

Listing 3: A snipper of the assembly program generated from the microthreaded
program of Matrix Multiplication for the Microgrid.

⬇

…

# Assembly code of thread matmul_inner

.ent matmul_inner

.registers 4 1 4 0 0 0

matmul_inner:

ldpc $l3

ldah $l3, 0($l3)

lda $l3, 0($l3)

$matmul_inner..ng:

ldah $l1,N($l3)

ldl $l1,N($l1)

mulq $l0,$l1,$l2

mulq $g2,$l1,$l1

addq $l2,$g3,$l2

addq $l1,$l0,$l0

s4addq $l2,$g1,$l2

s4addq $l0,$g0,$l0

ldl $l2,0($l2)

ldl $l0,0($l0)

mull $l2,$l0,$l0

addq $l0,$d0,$l0

mov $l0, $s0

end

.end matmul_inner

…

# to show the concurrency constructs in the ISA

.ent t_main

…

allocate/s $l0, 0, $l0

setstart $l0, 0

ldq $l1,matmul_outer($l17)

setlimit $l0, $l9

setstep $l0, 1

setblock $l0, 0

wmb

crei $l0, 0($l1)

putg $l12, $l0, 0

putg $l11, $l0, 1

putg $l10, $l0, 2

sync $l0, $l1

mov $l1, $31

release $l0

…

.end t_main

#### SL tool-chain

Figure 8: The SL tool-chain.

The SL tool-chain is shown in fig. 8 and is built around SL [22] which is a C
based language but is extended to express the concurrency constructs of the
microthreading model. SL is an intermediate language intended for higher level
programming languages (such as Single Assignment C or SAC [36, 13, 12, 14,
15], FastFlow [2, 1] etc.) and parallelizing C compiler [34, 35]. SAC is
Matlab-like programming language, and it provides concurrency from a very high
view. Programmer writes program using arrays and let the compiler decide to
exploit concurrency in the programs.

A number of tools and simulators are added to the designer’s toolbox and used
for the evaluation of the Microgrid from different perspective. The SL
compiler can generate binary for different implementations of the Microgrid.
We have software libraries that provide the run-time systems for the
microthreading model on the shared memory SMP machines and referred as _svp-
ptl_ [51] and distributed memory for clusters/grids and are referred as Hydra
[26] and _dsvp-ptl_ [50] The SL compiler can generate binary for UTLEON3 [9,
10], MGSim [5, 32] and HLSim [44, 45, 46, 43, 47, 48, 41, 42].

Unless specified otherwise, the SL compiler generates two implementations for
every family in the given SL program; concurrent and sequential. Either one is
used as per the dynamic state of the chip. In case resources can not be
allocated to a family, the sequential version can be used. The sequential
version of the program is used to avoid deadlock and if the deadlock can be
avoided by static analysis, then suspension on resource allocation is safe.
The programmer can force the program to use the concurrent version all the
time i.e. threads are suspended until resources become available.

##  6 The microthreading model in the context of the Microgrid

We gave details of the Microgrid, and would like to revisit the microthreading
model in the context of the Microgrid. We need to understand all the details
of the model and the architecture in order to simulate the architecture at a
high level, as the high-level simulator have to exhibit the same behavior.

###  6.1 A concrete example

Figure 9: A concrete example of the microthreaded program of the
microthreading model executing in the single core of the Microgrid. We
explicitly use a single core to show the coordination of different events in
different threads over time.

A concrete example of the microthreaded program in the microthreading model
executing in a single core of the Microgrid is shown in fig. 9. All
concurrency constructs are shown in the figure in the form of rectangles of
different sizes/color. We also show the effect of concurrency constructs on
the execution of threads. Every thread has an implicit _start_ and _end_
event. Threads are created at the rate of one thread per cycle. The creation
process takes 4 cycles (with additional latency to load the cache-line from
memory if not in the I-cache, also potential queueing delays if another family
is being created). The instructions of a thread can be executed as soon as the
thread is created which means the first instruction of the first thread can
execute along with the creation of the other threads [23]. The process of
creation of threads is implemented sequential on a single core, and is decided
based on the trade-off between simple design and efficient creation of family.
In the figure we can see that two _allocate_ events execute concurrently, but
the _create_ events are sequentialized on a single core.

We show a heterogeneous family of threads i.e. Threads $0$ and $1$ in Family
$0$ in the first level is different from each other. We show a dependent
family where threads are waiting for the previous threads to write the shared
variable/register. We also show that the sync event is waiting for all the
threads to complete. We show a homogeneous independent family where the parent
threads is executing along with the child threads and therefore the sync does
not wait as the time the sync is issued where all the created threads are
completed already.

###  6.2 Family’s Life cycle

A family passes through different stages in the Microgrid during the
execution. In this section we consider an example when a parent thread is
executing on a core and it delegates a family to a place of four cores shown
in fig. 10. A detailed explanation of these stages is given in below section.

Figure 10: The life cycle of a family during the execution in the Microgrid.

#### Allocation

It is implemented as try-to-allocate mechanism (see below for various options
on allocate). In this process; family context, thread contexts and registers
on all cores of the place are tried to be allocated. The parent thread sends a
message on the delegation network to the first core. The first core checks the
availability of at least one thread context, one family context and 31
registers. In case of success the message is passed to the next core of the
place using distribution network. When all the cores succeed, the message
comes back from the last to the first core on distribution network, and the
contexts are asynchronously allocated. The first core then notifies the parent
core using delegation network. The allocate protocol has three different
modes:

  * •

Normal (or default): The allocation fails immediately after the allocation
fails on any core in the place.

  * •

Suspend: The allocation waits for the availability of resources.

  * •

Exclusive: The allocation allocates exclusive contexts and in case of
unavailability, keeps waiting until resources are acquired.

The allocate protocol has four different strategies:

  * •

Normal (or default): It will try to allocate as many cores as requested,
possibly down to one core (in power of 2).

  * •

Exact: It will allocate the family on all the requested cores.

  * •

Single: It will allocate the entire family to the first core in the place.

  * •

Balanced: It will allocate the entire family to the least loaded core of the
place, in terms of family contexts.

#### Configuration

Once the contexts are allocated on the cores, the next message is sent on the
delegation network to the first core to store parameters in the allocated
family table entry for the bulk creation. It consists of $setstart$,
$setlimit$, $setstop$, $setblock$ etc. which are derived from the create
construct and defines the number of threads to be created per core. The
configuration process is completed asynchronously and does not need any
acknowledgement. Therefore as soon as the configuration message is issued, the
next message can also be sent. In the current implementation, the delegation
network preserves the order of messages i.e. configure messages will reach to
the destination before create message.

#### Creation

The create message is sent from the parent core to the first core in the place
via delegation network. As soon as the message is received by a core, thread
creation is started asynchronously and the message is forwarded to the next
core in the place. The first core will acknowledge the parent core when all
the threads on the first core are created. The parent core may then write the
global and/or shared registers to the first core through inter-context
communication and can continue with its instructions (if any) or wait for the
synchronization of the family.

When all the threads are created, the core can de-allocate the contexts that
are not really required e.g. at the time of allocation 31 registers were
allocated, but suppose a thread is created which only uses 15 registers
therefore the core will de-allocate the extra 16 registers. All the threads
continue their execution on the allocated core, and as the threads get
terminated the context get de-allocated asynchronously. Every core shares the
information when it completes executing the allocated threads of a given
family with the next core. The last core has the information that all the
threads in the family are completed.

#### Synchronization

When all threads in the family complete, the last core will send a message on
the delegation network to the parent core. The parent thread is activated so
that the family can be synchronized. All the modified state from the family
becomes defined. In the case of a dependent family, the parent core will also
read the value from the register updated by the last thread through inter-
context communication.

#### Release

A message is sent from the parent core to the first core on delegation network
to release the family. This process will complete asynchronously and the
parent core can continue its execution.

###  6.3 Thread’s life cycle

Figure 11: The lifecycle of a thread during the execution on the core of the
Microgrid.

A thread passes through different stages during the execution and is shown in
fig. 11. A newly created thread is allocated thread context, registers and PC
(Program counter) is configured to place the thread in ready queue. In case
the thread gets an I-cache miss the thread waits until the instructions are
loaded from cache. The thread then passes to the active queue. The context of
the thread is moved from the active queue to running where the instructions
actually execute in the execute stage of the pipeline. A thread can be
suspended when it is active or running at the write back stage of the pipeline
e.g. in case of dependency. The asynchronous completion of a thread moves the
thread from the suspended stage to ready queue. At the termination of the
thread the allocated entries are cleaned up which can be used by any newly
created threads.

###  6.4 Distribution of threads

Figure 12: Distribution of independent threads on 4 cores with 5 window size.

The distribution of threads to the cores in a place depends on the type of
family i.e. dependent or independent. The threads in a dependent family are
restricted to single core only, as no significant speedup can be obtained by
distributing them on multiple cores. However instructions in the thread will
get benefit from latency tolerance on asynchronous completion in loads, store
and floating point operations.

Threads of an independent family are distributed by an equal distribution of
threads per core. In fig. 12 we show an example of a family with 40 threads on
4 cores with window size of 5. Threads are distributed as 40/4 and every core
can create 10 threads. But the window size is 5 and therefore only 5 threads
can be activated at a time on a given core. As soon as a thread terminates, a
new thread can use the context of the terminated thread. For instance on core
x, threads 0,1 and 2 are terminated, threads 3-7 are executing and threads 8
and 9 are still waiting to be created.

###  6.5 Communication through registers

Figure 13: Allocation of registers to threads and their communication through
registers.

Every thread created in the Microgrid uses a set of registers in the register
file. The channels of the microthreading model used for the communication and
synchronization of the family introduced in Section 3.1 are implemented in
registers of the Microgrid. The registers allocated to a thread are
categorized as; globals, locals, shareds and dependents. The mapping of
registers to threads and their communication through registers is shown in
fig. 13. Some explanation of these registers are given as:

  * •

Global registers implements global channels and are visible to all threads in
the family. The parent thread writes to the global registers and all created
threads in the family can read from them.

  * •

Local registers are only visible to the individual thread only.

  * •

Dependent registers implements shared channels and have read-only access to
the shared registers from the previous threads.

  * •

Shared registers implements shared channels and have the write access by the
current threads, and carry the modified value to be read by the next thread.

##  7 I/O in the Microgrid

The Microgrid requires a decentralized approach where not every core is
connected to I/O but some specialized microthreaded cores are used to support
I/O and referred as I/O cores. I/O cores have limited/extended instruction set
[25] compared to the regular microthreaded core and has no floating point
operations. The instruction set of the I/O core supports the I/O
infrastructure and are connected to the delegation network of the Microgrid.
We do not simulate I/O cores in the current implementation of HLSim, therefore
we refer readers to [16, 21, 31] for the I/O management in the Microgrid.

##  8 Conclusion

The microthreading model is a hybrid dataflow model and provides the
simplicity of _von Neumann_ model and asynchronous completion of the
_dataflow_ execution model. It is an abstract machine model for many-cores
architecture and shifts the perspective from software threads to hardware
threads. Because of asynchronous completion and fine-grained latency tolerance
the microthreading model can potentially achieve the goal of RISC i.e. _one
instruction per cycle_ in the throughput of the program assuming single issue
width. The details of a particular type of future many-cores systems are given
to demonstrate the complexity of the architecture.

## Acknowledgement

The author would like to thank Dr. Raphael Poss, Dr. Michiel van Tol and Prof.
dr. Chris Jesshope.

## References

  * [1] Marco Aldinucci, Sonia Campa, Marco Danelutto, Peter Kilpatrick, and Massimo Torquati.  Targeting distributed systems in fastflow.  In Euro-Par 2012 Workshops, Proc. of the CoreGrid Workshop on Grids, Clouds and P2P Computing, LNCS. Springer, 2013.
  * [2] Marco Aldinucci, Marco Danelutto, Peter Kilpatrick, and Massimo Torquati.  Fastflow: high-level and efficient streaming on multi-core.  In in Programming Multi-core and Many-core Computing Systems, ser. Parallel and Distributed Computing, S. Pllana, page 13, 2012.
  * [3] Arvind, Rishiyur S. Nikhil, and Keshav K. Pingali.  I-structures: data structures for parallel computing.  ACM Trans. Program. Lang. Syst., 11:598–632, October 1989.
  * [4] A. Bolychevsky, C. R. Jesshope, and V. B. Muchnick.  Dynamic scheduling in risc architectures.  In IEE Proceedings Computers and Digital Techniques, volume 143, pages 309–317, 1996.
  * [5] K. Bousias, L. Guang, C. R. Jesshope, and M. Lankamp.  Implementation and evaluation of a microthread architecture.  J. Syst. Archit., 55:149–161, March 2009.
  * [6] Richard Buehrer and Kattamuri Ekanadham.  Incorporating data flow ideas into von neumann processors for parallel execution.  Computers, IEEE Transactions on, C-36(12):1515 –1522, dec. 1987\.
  * [7] Sorin Cotofana and Stamatis Vassiliadis.  On the design complexity of the issue logic of superscalar machines.  In Proceedings of the 24th Conference on EUROMICRO - Volume 1, EUROMICRO ’98, pages 10277–, Washington, DC, USA, 1998. IEEE Computer Society.
  * [8] D. E. Culler and Arvind.  Resource requirements of dataflow programs.  SIGARCH Comput. Archit. News, 16(2):141–150, May 1988.
  * [9] M. Danek, L. Kafka, L. Kohout, and J. Sykora.  Instruction set extensions for multi-threading in leon3.  In Design and Diagnostics of Electronic Circuits and Systems (DDECS), 2010 IEEE 13th International Symposium on, pages 237 –242, april 2010\.
  * [10] M. Daněk, L. Kafka, L. Kohout, J. Sýkora, and R. Bartosinski.  UTLEON3: Exploring Fine-Grain Multi-Threading in FPGAs.  Circuits and Systems. Springer, November 2012.
  * [11] Kourosh Gharachorloo, Daniel Lenoski, James Laudon, Phillip Gibbons, Anoop Gupta, and John Hennessy.  Memory consistency and event ordering in scalable shared-memory multiprocessors.  SIGARCH Comput. Archit. News, 18:15–26, May 1990.
  * [12] Clemens Grelck.  Shared memory multiprocessor support for functional array processing in SAC.  Journal of Functional Programming, 15(3):353–401, 2005.
  * [13] Clemens Grelck, Stephan Herhut, Chris Jesshope, Carl Joslin, Mike Lankamp, Sven-Bodo Scholz, and Alex Shafarenko.  Compiling the functional data-parallel language sac for microgrids of self-adaptive virtual processors.  In 14th Workshop on Compilers for Parallel Computing (CPC’09), IBM Research Center, Zurich, Switzerland, 2009.
  * [14] Clemens Grelck and Sven-Bodo Scholz.  SAC: A functional array language for efficient multithreaded execution.  International Journal of Parallel Programming, 34(4):383–427, 2006\.
  * [15] Clemens Grelck and Sven-Bodo Scholz.  Sac: off-the-shelf support for data-parallelism on multicores.  In Proceedings of the 2007 workshop on Declarative aspects of multicore programming, DAMP ’07, pages 25–33, New York, NY, USA, 2007. ACM.
  * [16] Michael A. Hicks, Michiel W. van Tol, and Chris R. Jesshope.  Towards Scalable I/O on a Many-core Architecture.  In International Conference on Embedded Computer Systems: Architectures, MOdeling and Simulation (SAMOS), pages 341–348. IEEE, July 2010\.
  * [17] R. A. Iannucci.  Toward a dataflow/von neumann hybrid architecture.  SIGARCH Comput. Archit. News, 16:131–140, May 1988.
  * [18] Chris Jesshope and Bing Luo.  Micro-threading: A new approach to future risc.  In Proceedings of the 5th Australasian Computer Architecture Conference, pages 34–, Washington, DC, USA, 2000. IEEE Computer Society.
  * [19] Chris Jesshope, Jean-Marc Philippe, and Michiel van Tol.  An Architecture and Protocol for the Management of Resources in Ubiquitous and Heterogeneous Systems Based on the SVP Model of Concurrency.  In SAMOS ’08: Proceedings of the 8th international workshop on Embedded Computer Systems, pages 218–228, Berlin, Heidelberg, 2008. Springer-Verlag.
  * [20] Chris R. Jesshope.  Multi-threaded microprocessors - evolution or revolution.  In Amos Omondi and Stanislav Sedukhin, editors, Advances in Computer Systems Architecture, 8th Asia-Pacific Conference, ACSAC 2003, Aizu-Wakamatsu, Japan, September 23-26, 2003, Proceedings, volume 2823 of Lecture Notes in Computer Science, pages 21–45. Springer, 2003.
  * [21] Raphael ‘kena’ Poss.  On the realizability of hardware microthreading—Revisting the general-purpose processor interface: consequences and challenges.  PhD thesis, University of Amsterdam, 2012.
  * [22] Raphael ‘kena’ Poss.  SL—a “quick and dirty” but working intermediate language for SVP systems.  Technical Report arXiv:1208.4572v1 [cs.PL], University of Amsterdam, August 2012.
  * [23] Mike Lankamp.  Design and evaluation of a microthreaded many-cores architecture.  PhD thesis, University of Amsterdam, 2012.
  * [24] Mike Lankamp and Raphael Poss.  Microgrid places and work addressing.
  * [25] Mike Lankamp, Michiel W. van Tol, Chris Jesshope, and Raphael Poss.  Hardware I/O interface on the Microgrid.
  * [26] Andrei Matei.  Towards Adaptable Parallel Software - the Hydra Runtime for SVP Programs.  November 2010.
  * [27] Raphael ’kena’ Poss Mike Lankamp.  Sl library: dynamic place allocation.
  * [28] David Mosberger.  Memory consistency models.  SIGOPS Oper. Syst. Rev., 27:18–26, January 1993.
  * [29] Gregory M. Papadopoulos and David E. Culler.  Monsoon: an explicit token-store architecture.  In 25 years of the international symposia on Computer architecture (selected papers), ISCA ’98, pages 398–407, New York, NY, USA, 1998\. ACM.
  * [30] James L. Peterson and Theodore A. Norman.  Buddy systems.  Commun. ACM, 20(6):421–431, June 1977.
  * [31] Raphael Poss, Mike Lankamp, Irfan Uddin, Jaroslav Sýkora, and Leoš Kafka.  Heterogeneous integration to simplify many-core architecture simulations.  In Proceedings of the 2012 Workshop on Rapid Simulation and Performance Evaluation: Methods and Tools, RAPIDO ’12, pages 17–24, New York, NY, USA, 2012. ACM.
  * [32] Raphael Poss, Mike Lankamp, Qiang Yang, Jian Fu, Irfan Uddin, and Chris Jesshope.  MGSim - A simulation environment for multi-core research education.  SAMOS, 2013.  (To appear).
  * [33] Rahul Razdan, Karl S. Brace, and Michael D. Smith.  Prisc software acceleration techniques.  In Proceedings of the1994 IEEE International Conference on Computer Design: VLSI in Computer & Processors, ICCS ’94, pages 145–149, Washington, DC, USA, 1994. IEEE Computer Society.
  * [34] Dimitris Saougkos, Despina Evgenidou, and George Manis.  Specifying loop transformations for C2$\mu$TC source-ro-source compiler.  In Proc. of 14th Workshop on Compilers for Parallel Computing (CPC’09), Zürich, Switzerland. IBM Research Center, January 2009.
  * [35] Dimitris Saougkos and George Manis.  Run-time scheduling with the C2uTC parallelizing compiler.  In 2nd Workshop on Parallel Programming and Run-Time Management Techniques for Many–Core Architectures, in Workshop Proceedings of the 24th Conference on Computing Systems (ARCS 2011), Lecture Notes in Computer Science, pages 151–157. Springer, 2011.
  * [36] Sven-Bodo Scholz, Stephan Herhut, Frank Penczek, and Clemens Grelck.  Sac 1.0 – single assignment c – tutorial.  2010\.
  * [37] J.L. Shin, K. Tam, D. Huang, B. Petrick, H. Pham, Changku Hwang, Hongping Li, A. Smith, T. Johnson, F. Schumacher, D. Greenhill, A.S. Leon, and A. Strong.  A 40nm 16-core 128-thread cmt sparc soc processor.  In Solid-State Circuits Conference Digest of Technical Papers (ISSCC), 2010 IEEE International, pages 98 –99, 2010.
  * [38] Gurindar S. Sohi, Scott E. Breach, and T. N. Vijaykumar.  Multiscalar processors.  SIGARCH Comput. Archit. News, 23:414–425, May 1995.
  * [39] Kyriakos Stavrou, Paraskevas Evripidou, and Pedro Trancoso.  Ddm-cmp: Data-driven multithreading on a chip multiprocessor.  In SAMOS’05, pages 364–373, 2005.
  * [40] Steven Swanson, Andrew Schwerin, Martha Mercaldi, Andrew Petersen, Andrew Putnam, Ken Michelson, Mark Oskin, and Susan J. Eggers.  The wavescalar architecture.  ACM Trans. Comput. Syst., 25:4:1–4:54, May 2007.
  * [41] Irfan Uddin.  High-level simulation of the Microgrid.  Master’s thesis, University of Amsterdam, Amsterdam, the Netherlands, August 2009.
  * [42] Irfan Uddin, Chris R. Jesshope, Michiel W. van Tol, and Raphael Poss.  Collecting signatures to model latency tolerance in high-level simulations of microthreaded cores.  In Proceedings of the 2012 Workshop on Rapid Simulation and Performance Evaluation: Methods and Tools, RAPIDO ’12, pages 1–8, New York, NY, USA, 2012. ACM.
  * [43] Irfan Uddin, Raphael Poss, and Chris Jesshope.  Cache-based high-level simulation of microthreaded many-core architectures.  Journal of System Architecture, 2013.
  * [44] Irfan Uddin, Raphael Poss, and Chris Jesshope.  Multiple levels of abstraction in the simulation of microthreaded many-core architectures.  Simulation Modelling Practice and Theory, 2013.
  * [45] Irfan Uddin, Raphael Poss, and Chris Jesshope.  One-IPC high-level simulation of microthreaded many-core architectures.  Simulation Modelling Practice and Theory, 2013.
  * [46] Irfan Uddin, Raphael Poss, and Chris Jesshope.  Signature-based high-level simulation of microthreaded many-core architectures.  Microprocessors and Microsystems, 2013.  (Submitted, but not yet reviewed).
  * [47] Irfan Uddin, Raphael Poss, and Chris Jesshope.  Analytical-based high-level simulation of microthreaded many-core architectures.  In PDP, February 2014.  (Submitted, but not yet reviewed).
  * [48] Irfan Uddin, Michiel W. van Tol, and Chris R. Jesshope.  High-level simulation of SVP many-core systems.  Parallel Processing Letters, 21(4):413–438, December 2011.
  * [49] Michiel W. van Tol.  A characterization of the SPARC T3-4 system.  ArXiv e-prints, abs/1106.2992, June 2011.
  * [50] Michiel W. van Tol and Juha Koivisto.  Extending and implementing the self-adaptive virtual processor for distributed memory architectures.  ArXiv e-prints, abs/1104.3876, April 2011.
  * [51] M.W. van Tol, C.R. Jesshope, M. Lankamp, and S. Polstra.  An implementation of the sane virtual processor using posix threads.  Journal of Systems Architecture, 55(3):162–169, 2009.  Challenges in self-adaptive computing (Selected papers from the Aether-Morpheus 2007 workshop).
  * [52] Thuy Duong Vu and Chris Jesshope.  Formalizing sane virtual processor in thread algebra.  In Proceedings of the formal engineering methods 9th international conference on Formal methods and software engineering, ICFEM’07, pages 345–365, Berlin, Heidelberg, 2007. Springer-Verlag.
  * [53] W.-D. Weber and A. Gupta.  Exploring the benefits of multiple hardware contexts in a multiprocessor architecture: preliminary results.  SIGARCH Comput. Archit. News, 17(3):273–280, April 1989.
  * [54] Wen yen Lin and Jean luc Gaudiot.  The design of i-structure software cache system.  In In Workshop on Multithreaded Execution, Architecture and Compilation, 1998.


# On the Prym variety of genus $3$ covers of genus $1$ curves

Christophe Ritzenthaler and Matthieu Romagny

###### Abstract

Given a generic degree-$2$ cover of a genus 1 curve $D$ by a non-hyperelliptic
genus $3$ curve $C$ over a field $k$ of characteristic different from $2$, we
produce an explicit genus $2$ curve $X$ such that $\operatorname{Jac}(C)$ is
isogenous to $\operatorname{Jac}(D)\times\operatorname{Jac}(X)$. This
construction can be seen as a degenerate case of Bruin’s result [8].

  *     * Keywords. genus $3$ curves; plane quartics; Prym variety; singular covers

2010 Mathematics Subject Classification. 14Q05

[Français]

Titre. Sur la variété de Prym des revêtements de genre $3$ des courbes de
genre $1$ Résumé. Étant donné un revêtement de degré $2$ générique d’une
courbe $D$ de genre $1$ par une courbe non-hyperelliptique $C$ de genre $3$
sur un corps $k$ de caractéristique différente de $2$, nous produisons une
courbe explicite $X$ de genre $2$ dont la jacobienne $\operatorname{Jac}(C)$
est isogène à $\operatorname{Jac}(D)\times\operatorname{Jac}(X)$. Cette
construction peut être vue comme un cas dégénéré du résultat de Bruin [8].

###### Contents

  1. 1\. Introduction
  2. 2\. From a singular cover to the original cover
  3. 3\. The singular cover as a special fiber

##  1\. Introduction

Let $C$ be a (smooth, projective, absolutely irreducible) curve of genus
$g_{C}\geqslant 2$ over a field $k$. Let us assume that $C$ admits a
degree-$n$ map $\pi$ to a curve $D/k$ of genus $g_{D}$ with $0<g_{D}<g_{C}$.
We then know that $\operatorname{Jac}(C)$ is isogenous to
$\operatorname{Jac}(D)\times A$ and one would like to get as much information
as possible on $A$ from $\pi$. For instance, if $C$ is given by explicit
equations, is it possible to find a curve $X/k$ given by explicit equations
such that $A$ is isogenous over $k$ to $\operatorname{Jac}(X)$? There is an
extensive literature dedicated to the case $g_{C}=2$ for which $D$ and $X$ are
genus $1$ curves, both for its applications to cryptography (see [14], [10]
and [4]) and for its interests in pure mathematics [15]. The general theory is
well understood (see for instance [20]) and explicit formulas have been worked
out when $n=2$ (going back to the work of Jacobi on abelian integrals, see the
references in [2, p.395] or [19]), $n=3$ (see [18], [22] or the appendix of
[7]), $n=4$ (see [5] and [9]), $n=5$ (see [25]) and more generally when
$n\leqslant 11$ (see [23]). From now on, let $n=2$. When $C$ is given by a
hyperelliptic equation, we can describe the map $\pi$ as the quotient by the
involution $(x,y)\mapsto(-x,y)$. Then $C:y^{2}=f(x^{2})$ where $f$ is a
polynomial of degree $g_{C}+1$ and hence $D:y^{2}=f(x)$ is a curve of genus
$g_{D}=\lceil\frac{g_{C}+1}{2}\rceil-1$. One can moreover take advantage of
the existence of the hyperelliptic involution to construct the curve
$X:y^{2}=xf(x)$ which is the quotient of $C$ by $(x,y)\mapsto(-x,-y)$. It is
easy to see by the action on the differentials that
$\operatorname{Jac}(C)\sim\operatorname{Jac}(D)\times\operatorname{Jac}(X)$.
Apart from the hyperelliptic cases described above, for a generic curve $C$, a
curve $X$ has been made explicit only in few cases. One is when $D$ is
hyperelliptic and $C$ is a degree-2 cover either étale or ramified at two
points, see respectively [26, p.346] and [24]. In [8], one can find the only
case where $D$ is neither elliptic nor hyperelliptic, namely $g_{C}=5$ and
$g_{D}=3$. This work relies on beautiful geometric constructions sketched in
[1, VI exercise F]. We will use this construction to get our result. The
present article deals with the case where $C$ is a non-hyperelliptic curve of
genus $3$ with a degree-$2$ map to a genus $1$ curve $D$ over a field $k$ of
characteristic different from $2$. It finds its motivation in the article [28]
where cohomological techniques are derived to compute the Weil polynomial of
$C$. Although the techniques developed there remain interesting on their own,
one byproduct of the present article is that the computation of the Weil
polynomial of $C$ can be reduced to computations in genus 1 and 2. Note that
any degree-2 cover of a genus $1$ curve by a non-hyperelliptic genus $3$ curve
$C$ can be written in the form $y^{4}-h(x,z)y^{2}+r(x,z)=0$ with $r$ a degree
$4$ polynomial, since we can assume that the involution of $C$ which defines
the cover is given by $(x:y:z)\mapsto(x:-y:z)$. Our main result gives an
equation of $X$ when $r$ splits as a product of degree 2 factors.

###### Theorem 1.1

Let $C$ be a smooth, non-hyperelliptic genus $3$ curve defined by

$C:y^{4}-h(x,z)\,y^{2}+f(x,z)\,g(x,z)=0$

in $\mathbf{P}^{2}$ where

$f=f_{2}x^{2}+f_{1}xz+f_{0}z^{2},\quad g=g_{2}x^{2}+g_{1}xz+g_{0}z^{2},\quad
h=h_{2}x^{2}+h_{1}xz+h_{0}z^{2}$

are homogeneous degree-2 polynomials over a field $k$ of characteristic
different from $2$. The involution $(x:y:z)\mapsto(x:-y:z)$ induces a degree-2
cover $\pi$ to the genus $1$ curve

$D:y^{2}-h(x,z)\,y+f(x,z)\,g(x,z)=0$

in the weighted projective space $\mathbf{P}{(1,2,1)}$. Let

$A=\begin{bmatrix}f_{2}&f_{1}&f_{0}\\\ h_{2}&h_{1}&h_{0}\\\
g_{2}&g_{1}&g_{0}\end{bmatrix}$

and assume that $A$ is invertible. Let

${A^{-1}}=\begin{bmatrix}a_{1}&b_{1}&c_{1}\\\ a_{2}&b_{2}&c_{2}\\\
a_{3}&b_{3}&c_{3}\end{bmatrix}.$

Then
$\operatorname{Jac}(C)\sim\operatorname{Jac}(D)\times\operatorname{Jac}(X)$
with $X\simeq y^{2}=b\cdot(b^{2}-ac)$ in $\mathbf{P}{(1,3,1)}$ where

$a=a_{1}+2a_{2}x+a_{3}x^{2},\quad b=b_{1}+2b_{2}x+b_{3}x^{2},\quad
c=c_{1}+2c_{2}x+c_{3}x^{2}.$

###### Remark 1.2

The geometric hypothesis (i.e. which is still true over $\bar{k}$) that
$\det(A)\neq 0$ is satisfied if $C$ has automorphism group isomorphic to
$\mathbf{Z}/2\mathbf{Z}$. Indeed since $C$ is non-singular over $\bar{k}$, we
can assume that $f=xz$, $g=x^{2}+g_{1}xz+z^{2}$ ($fg$ has no double root). If
$A$ is non-invertible, we have for instance that $h=\lambda f+\mu g$ but then
the morphism $(x:y:z)\mapsto(z:y:x)$ is also an involution. In that case, the
Jacobian is going to decompose further in a product of three genus $1$ curves
which are easily determined.

###### Remark 1.3

The arithmetic hypothesis that $r=fg$ over $k$ is however necessary in our
proof and we do not know how to remove it. Note that it can however always be
obtained over a finite extension of $k$.

After we wrote this article, it was brought to our attention by Victor Enolski
and Yuri Fedorov that such a case was already handled by Kötter in 1892 (see
[21] and also [13, Eq.(2–11)]) in an analytic setting. The proof we propose
here is completely different as it is algebraic and works over any field (of
characteristic not $2$). The shape of the equation we get for $X$ is also much
simpler and in particular does not involve any field extension of $k$. The
general strategy is somehow new in this context although it will probably
appear very classical to algebraic geometers. The idea is to move from the
smooth cover $\pi:C\to D$ to a singular one
$\tilde{\pi}:\tilde{C}\to\tilde{D}$ of arithmetic genus $5$ and $3$, with
$\tilde{C}$ birational to $C$. The reason to do so is the following. As $n=2$,
one can look at $A$ as the Prym variety $P(C/D)$, i.e. the connected component
of the identity of
$\ker(\pi_{*}:\operatorname{Jac}(C)\to\operatorname{Jac}(D))$. Now, the Prym
variety of a degree-2 cover $\pi$ naturally inherits a principal polarization
from $\operatorname{Jac}(C)$ when $\pi$ is étale (see for instance [26,
Cor.2]). Our original smooth cover $\pi$ _is not_ étale but the cover
$\tilde{\pi}$ will only be ramified over the singular points of $\tilde{D}$.
In this case (more precisely in the case of _allowable covers_ , see below),
Beauville showed that the generalized Prym variety of $\tilde{\pi}$ is an
abelian surface $P(\tilde{C}/\tilde{D})$, isogenous to $P(C/D)$, and naturally
principally polarized. The abelian variety $P(\tilde{C}/\tilde{D})$ is
therefore the Jacobian of a (possibly reducible) genus $2$ curve $X$. It then
remains to find $X$ explicitly. In order to do so, we look at the cover
$\tilde{C}\to\tilde{D}$ as the degeneration of a family of unramified
degree-$2$ covers $\mathcal{C}\to\mathcal{D}$ of smooth genus $3$ curves by
smooth degree $5$ curves. As we said, for the smooth generic fiber, Bruin [8]
gives explicitly the hyperelliptic curve $\mathcal{X}$ whose Jacobian is the
Prym of the cover. Using a particular deformation, we show that we can
specialize the equation of $\mathcal{X}$ to find $X$.

### Acknowledgements

We want to thank Jeroen Sijsling for his comments on an earlier version of the
paper and Abhinav Kumar, Victor Enolski and Yuri Fedorov for their references
on the subject.

##  2\. From a singular cover to the original cover

Let the notation and hypotheses be as in Theorem 1.1 and let us consider the
curve in $\mathbf{P}^{4}$ defined by

$\tilde{C}:\begin{cases}x_{1}x_{2}&=f(u,v)\\\ x_{2}^{2}+x_{1}x_{3}&=h(u,v)\\\
x_{2}x_{3}&=g(u,v)\end{cases}$

Multiplying the second equation by $x_{2}^{2}$ and substituting the first and
last equation we get our initial curve

$C:x_{2}^{4}-h(u,v)x_{2}^{2}+f(u,v)g(u,v)=0.$

Hence we get an isomorphism between $C$ and $\tilde{C}$ on the locus
$x_{2}\neq 0$.
Now let us rewrite $\tilde{C}$ using the matrix $A$. We have

$\tilde{C}:\textrm{Id}\cdot\begin{bmatrix}x_{1}x_{2}\\\
x_{2}^{2}+x_{1}x_{3}\\\
x_{2}x_{3}\end{bmatrix}={A}\cdot\begin{bmatrix}u^{2}\\\ uv\\\
v^{2}\end{bmatrix}.$

As $A$ is invertible, we get:

$\tilde{C}:{A^{-1}}\begin{bmatrix}x_{1}x_{2}\\\ x_{2}^{2}+x_{1}x_{3}\\\
x_{2}x_{3}\end{bmatrix}=\begin{bmatrix}u^{2}\\\ uv\\\ v^{2}\end{bmatrix}.$

Let
$(q_{1}(x_{1},x_{2},x_{3}),q_{2}(x_{1},x_{2},x_{3}),q_{3}(x_{1},x_{2},x_{3}))$
be the left-hand side vector, we get that

$\tilde{C}:\begin{cases}q_{1}&=u^{2}\\\ q_{2}&=uv\\\ q_{3}&=v^{2}\end{cases}$

is a degree $2$ cover $\tilde{\pi}$ of the curve
$\tilde{D}:q_{2}^{2}=q_{1}q_{3}$. In order to see that the covers $\pi$ and
$\tilde{\pi}$ are birationally equivalent, let us consider the automorphism
$(x_{2}:u:v)\mapsto(-x_{2}:u:v)$ of $C$ which induces the cover $\pi:C\to D$.
On $\tilde{C}$, this automorphism induces the automorphism
$(x_{1}:x_{2}:x_{3}:u:v)\mapsto(-x_{1}:-x_{2}:-x_{3}:u:v)$ since
$x_{1}x_{2}=f(u,v)$ and $x_{2}x_{3}=g(u,v)$. But
$(-x_{1}:-x_{2}:-x_{3}:u:v)=(x_{1}:x_{2}:x_{3}:-u:-v)$ and hence the
automorphism is $\tilde{\iota}$ which induces the cover
$\tilde{\pi}:\tilde{C}\to\tilde{D}$. In particular $D$ is birationally
equivalent to $\tilde{D}$ over $k$. To conclude, let us study the singular
points of $\tilde{C}$. Since $C$ is non-singular, they can appear only when
$x_{2}=0$. But from the first form of the equations of $\tilde{C}$, we see
that $f(u,v)=g(u,v)=0$. Since $C$ is non-singular, $f$ and $g$ have no common
root, hence $u=v=0$. The possible singular points are then only the points
$p_{0}=(0:0:1:0:0)$ and $p_{\infty}=(1:0:0:0:0)$. The tangent cone at the
point $p_{0}$ has equations $x_{1}=x_{2}=f(u,v)=0$ while the tangent cone at
the point $p_{\infty}$ has equations $x_{2}=x_{3}=g(u,v)=0$ (see for instance
[27, III, § 3] or [11, p.485]). Since $f$ and $g$ have no double root, it
follows that these points are nodal singularities. Therefore we see that : (*)
The fixed points of the involution $\tilde{\iota}$ are exactly the singular
points, which are nodal, and $\tilde{\iota}$ preserves the branches at these
points. This condition is phrased in Beauville [3, p.157]. Since the map
$\tilde{\pi}$ is ramified at a point $p=(a:b:c:d:e)$ if and only if
$\tilde{\iota}(p)=p$, i.e. if and only if $d=e=0$ and $ab=0,bc=0,b^{2}+ac=0$,
we see moreover that $\tilde{\pi}$ is ramified only at the points $p_{0}$ and
$p_{\infty}$, in other words: (**) The cover $\tilde{\pi}$ is unramified away
from the singular locus. In Donagi and Livné [12], covers satisfying
conditions (*) and (**) are called allowable (also _admissible_ by other
authors) and we keep this terminology. Finally we sum up the preceding
discussion.

###### Proposition 2.1

The cover $\tilde{\pi}:\tilde{C}\to\tilde{D}$ is birationally equivalent to
the cover $\pi:C\to D$ and is allowable.

Let us associate to the cover $\tilde{C}\to\tilde{D}$ the connected component
containing $0$ of the kernel of the norm map
$\tilde{\pi}_{*}:\operatorname{Jac}(\tilde{C})\to\operatorname{Jac}(\tilde{D})$
between generalized Jacobians. We denote it $P(\tilde{C}/\tilde{D})$ and call
it the _generalized Prym variety_. Since the cover $\tilde{C}\to\tilde{D}$ is
allowable, the results [3, Prop.3.5] and [12, Lem.1] show that
$P(\tilde{C}/\tilde{D})$ is an abelian variety which is isogenous to the
classical Prym variety $P(C/D)$ of the ramified cover $C\to D$. Moreover the
kernel of the isogeny is contained in the group generated by degree $0$
divisors supported on the singular points of $\tilde{C}$ and is therefore
defined over $k$. We hence get:

###### Lemma 2.2

The Jacobian of $C$ is isogenous over $k$ to $D\times P(\tilde{C}/\tilde{D})$.

As mentioned in the introduction, what we have gained by moving from $P(C/D)$
to $P(\tilde{C}/\tilde{D})$ is that the latter is principally polarized [3,
Th.3.7]. From Weil (see the version in [17, Thm. 3.1]), one knows that every
principally polarized abelian surface is either the Jacobian of a curve, the
product of two elliptic curves (with the product polarization) or the
restriction of scalars of an elliptic curve over a quadratic extension of $k$.
Under our hypotheses, we are now going to recover $P(\tilde{C}/\tilde{D})$ as
the Jacobian of a genus $2$ curve $X$.

##  3\. The singular cover as a special fiber

In order to find explicitly the curve $X$, we will ‘embed’ our singular cover
$\tilde{C}\to\tilde{D}$ into a flat family whose generic fibre is non-singular
and use the beautiful result of [8] which we recall here.

###### Proposition 3.1

Let $Y\to Z$ be an unramified double cover of a genus $5$ curve over a non-
hyperelliptic curve of genus $3$ over a field $k$ of characteristic different
from $2$. Then such a cover can be written $Z:Q_{1}Q_{3}=Q_{2}^{2}$ where
$Q_{i}$ ($i=1,2,3$) are quadratic forms, and

$Y:\begin{cases}Q_{1}&=u^{2}\\\ Q_{2}&=uv\\\ Q_{3}&=v^{2}\end{cases}.$

Moreover the Prym variety $\operatorname{Prym}(Y/Z)$ (as a principally
polarized abelian surface over $k$) is the Jacobian of the hyperelliptic curve
$H$ which is the projective closure of the curve with equation
$y^{2}=-\det(Q_{1}+2xQ_{2}+x^{2}Q_{3})$, where we identify $Q_{i}$ with the
symmetric $3\times 3$ matrices $((\partial^{2}Q_{i}/\partial x_{j}\partial
x_{k}))_{1\leqslant j,k\leqslant 3}$.

###### Remark 3.2

Bruin’s result is stated in characteristic $0$ only. But all his arguments
work as well in positive characteristic different from $2$.

The _discriminant_ $\operatorname{Disc}(F)$ of a degree $4$ homogeneous
polynomial $F(x_{1},x_{2},x_{3})$ over a field $K$ of characteristic different
from $2$ is defined as the multivariate resultant of the partial derivatives
of $F$ (see [16, p.426]). It is a polynomial of degree $27$ in the
coefficients of a generic quartic and $\operatorname{Disc}(F)=0$ if and only
if the curve defined by $F$ is singular [16, Chap.13.1.D]. If we restrict the
discriminant to quartics $F$ of the form $Q_{2}^{2}-Q_{1}Q_{3}$ where

$Q_{i}=\sum_{i_{1}+i_{2}+i_{3}=2}a_{i_{1}i_{2}i_{3}}^{(i)}x_{1}^{i_{1}}x_{2}^{i_{2}}x_{3}^{i_{3}}$

are degree $2$ homogeneous polynomials over $K$, we get a homogeneous
polynomial $H$ of degree $2\cdot 27=54$ in the coefficients of the $Q_{i}$.
Note that $H$ is nonzero since for instance the quartic

$x_{1}^{4}-x_{2}^{4}+x_{3}^{4}=(x_{1}^{2})^{2}-(x_{2}^{2}+x_{3}^{2})\cdot(x_{2}^{2}-x_{3}^{2})$

has a discriminant equal to $-2^{40}$. The equation $H$ defines a hypersurface
in

$V=\operatorname{Spec}K[a_{i_{1}i_{2}i_{3}}^{(i)}]\simeq\mathbb{A}^{18}.$

The point $x_{\tilde{D}}$ representing the singular quartic
$\tilde{D}=q_{2}^{2}-q_{1}q_{3}$ belongs to $H$ and the pencil

$(Q_{1}(\lambda),Q_{2}(\lambda),Q_{3}(\lambda))=(q_{1}+\lambda
q_{1}^{\prime},q_{2}+\lambda q_{2}^{\prime},q_{3}+\lambda
q_{3}^{\prime}),\quad\lambda\in\mathbb{A}^{1}$

such that

$q_{1}^{\prime}=(x_{2}^{2}+x_{3}^{2})-q_{1},\quad
q_{2}^{\prime}=x_{1}^{2}-q_{2},\quad
q_{3}^{\prime}=(x_{2}^{2}-x_{3}^{2})-q_{3}$

is not contained in $H$ so its generic element is smooth. Now, let
$\mathcal{S}$ be the spectrum of the discrete valuation ring $R=k[[\epsilon]]$
with special fiber $k$ and generic fiber $K$. Over $\mathcal{S}$ we can define
a cover $\pi^{\textrm{\tiny def}}:\mathcal{C}\to\mathcal{D}$ by

$\mathcal{C}:\begin{cases}Q_{1}(\epsilon)&=u^{2}\\\ Q_{2}(\epsilon)&=uv\\\
Q_{3}(\epsilon)&=v^{2}\end{cases}\to\mathcal{D}:Q_{2}(\epsilon)^{2}-Q_{1}(\epsilon)Q_{3}(\epsilon)=0.$

Clearly $\pi^{\textrm{\tiny def}}$ is a deformation of
$\tilde{\pi}:\tilde{C}\to\tilde{D}$ and by construction its generic fiber
$\pi_{K}:\mathcal{C}_{K}\to\mathcal{D}_{K}$ is smooth over $K$. The Prym
varieties of the fibres of $\pi^{\textrm{\tiny def}}$ fit in a flat family
which we call the _Prym scheme_ $\mathcal{P}=P(\mathcal{C}\to\mathcal{D})$.
The details of its construction are to be found in [3], Section 6, especially
(6.2); we recall them briefly. The morphism $\pi^{\textrm{\tiny
def}}_{*}:\operatorname{Pic}^{0}(\mathcal{C})\to\operatorname{Pic}^{0}(\mathcal{D})$
is surjective with smooth target hence it is flat, and its fibres are smooth.
Therefore the group scheme $\ker(\pi^{\textrm{\tiny def}}_{*})\to\mathcal{S}$
is smooth and we let $\mathcal{P}\to\mathcal{S}$ denote the connected
component of the unit section. This is the Prym scheme; it has proper fibres
hence it is an abelian scheme. Using Proposition 3.1 as well as the fact that
the functor $\operatorname{Pic}^{0}$ commutes with base change, we get the
following lemma.

###### Lemma 3.3

The special fiber of $\mathcal{P}$ is $P(\tilde{C}/\tilde{D})$ and the generic
fiber is $P(\mathcal{C}_{K}/\mathcal{D}_{K})=\operatorname{Jac}(X_{K})$ where
$X_{K}:y^{2}=-\det(Q_{1}(\epsilon)+2xQ_{2}(\epsilon)+x^{2}Q_{3}(\epsilon))$.

Let $\mathcal{X}/\mathcal{S}$ be the projective closure of
$\operatorname{Spec}(R[x,y]/(y^{2}+\det(Q_{1}(\epsilon)+2xQ_{2}(\epsilon)+x^{2}Q_{3}(\epsilon))$
in the weighted projective space $\mathbf{P}^{(1,3,1)}$, in other words the
projective hypersurface described by the homogenized equation. The special
fiber $X=\mathcal{X}\otimes k$ is the completion of

$y^{2}=-\det(Q_{1}(0)+2xQ_{2}(0)+x^{2}Q_{3}(0))=-\det(q_{1}+2xq_{2}+x^{2}q_{3}).$

We are going to prove the following lemma.

###### Lemma 3.4

The scheme $\mathcal{X}$ is smooth over $\mathcal{S}$ with geometrically
connected fibres.

  * Proof.

As we are considering our schemes in the weighted projective space
$\mathbf{P}{(1,3,1)}$, the point at infinity is smooth and we only have to
consider the affine part in what follows. Since the generic fiber $X_{K}$ is
smooth, we need to consider the singular points of the special fiber $X$. They
correspond to points where $F(x)=\det(q_{1}+2xq_{2}+x^{2}q_{3})$ has a
(projective) root with multiplicity greater than 1. With the notation of
Theorem 1.1, since

$\begin{bmatrix}q_{1}\\\ q_{2}\\\
q_{3}\end{bmatrix}=\begin{bmatrix}a_{1}&b_{1}&c_{1}\\\ a_{2}&b_{2}&c_{2}\\\
a_{3}&b_{3}&c_{3}\end{bmatrix}\begin{bmatrix}x_{1}x_{2}\\\
x_{2}^{2}+x_{1}x_{3}\\\ x_{2}x_{3}\end{bmatrix}$

we have $F=b\cdot(b^{2}-ac)$. We are actually going to prove that $F$ has no
multiple root. As this is a geometric problem, we can assume that we work over
an algebraically closed field. In that case, since $C$ is assumed to be non-
singular, we can take $f(x,z)=xz$ and $g(x,z)=g_{2}x^{2}+g_{1}xz+z^{2}$. A
computation with a computer algebra system such as Magma shows that

$\textrm{Disc}(F)=\frac{4\cdot
g_{2}\cdot(g_{2}-g_{1}^{2}/4)^{2}\cdot\textrm{Disc}(h^{2}-4fg)}{\det(A)^{18}}.$

Since the curve $D$ is assumed to be non-singular, we see that $4fg-h^{2}$ has
no multiple root, hence $\textrm{Disc}(h^{2}-4fg)\neq 0$. The curve $C$ being
non-singular, one has that $g_{2}\neq 0$ (otherwise $(1:0:0)$ would be a
singular point) and one finds that $g$ does not have a double root, hence
$g_{2}-g_{1}^{2}/4\neq 0$. We hence get $\textrm{Disc}(F)\neq 0$. Finally,
since $\mathcal{X}\to\mathcal{S}$ is smooth and proper, the number of
connected components of the fibres is constant on $\mathcal{S}$, hence equal
to $1$. $\Box$

With this result on $\mathcal{X}$, we have the right hypotheses to apply the
following proposition (see for instance [6, Th. 9.5/1]).

###### Proposition 3.5

$\operatorname{Pic}^{0}(\mathcal{X})$ is a Néron model of
$\operatorname{Jac}(X_{K})$.

We can now conclude. By Lemma 3.3, the Néron model of the Jacobian of $X_{K}$
is the Néron model of the generic fiber $P(\mathcal{C}_{K}/\mathcal{D}_{K})$
of $\mathcal{P}$. Since the special fiber of $\mathcal{P}$ is
$P(\tilde{C}/\tilde{D})$ which is an abelian variety (the cover $\tilde{\pi}$
being allowable), we see that the Néron model of
$P(\mathcal{C}_{K}/\mathcal{D}_{K})$ is $\mathcal{P}$. Hence the Néron model
of $\operatorname{Jac}(X_{K})$ is $\mathcal{P}$ and by Proposition 3.5 we have
$\mathcal{P}=\operatorname{Pic}^{0}(\mathcal{X})$. Taking the special fiber
gives:

$\mathcal{P}\otimes
k=P(\tilde{C}/\tilde{D})=\operatorname{Pic}^{0}(\mathcal{X})\otimes
k=\operatorname{Jac}(\mathcal{X}\otimes k)=\operatorname{Jac}(X).$

We have therefore obtained a description of $P(\tilde{C}/\tilde{D})$ which is
isogenous to $P(C/D)$ and this concludes the proof of Theorem 1.1.

## References

  * [1] E. Arbarello, M. Cornalba, P. Griffiths, and J. Harris, _Geometry of algebraic curves, Vol. I_ , Grundlehren der Mathematischen Wissenschaften, vol. 267, Springer-Verlag, New-York, 1985. MR-0770932
  * [2] H. F. Baker, _Abelian functions._ Abel’s theorem and the allied theory of theta functions. Reprint of the 1897 original, with a foreword by Igor Krichever. Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1995. MR-1386644
  * [3] A. Beauville, _Prym varieties and the Schottky problem_ , Invent. Math. 41 (1977), no. 2, 149–196. MR-0572974
  * [4] D. J. Bernstein and T. Lange, _Hyper-and-elliptic-curve cryptography_ , LMS J. Comput. Math. 17 (2014), suppl. A, 181–202. MR-3240803
  * [5] O. Bolza, _Über die Reduction hyperelliptischer Integrale erster Ordnung und erster Gattung auf elliptische durch eine Transformation vierten Grades_ , Math. Ann. 28 (1887), 447–456. MathDoc
  * [6] S. Bosch, W. Lütkebohmert, and M. Raynaud, _Néron models_ , Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 21, Springer-Verlag, Berlin, 1990. MR-1045822
  * [7] R. Bröker, E. W. Howe, K. E. Lauter, and P. Stevenhagen, _Genus-2 curves and Jacobians with a given number of points_ , LMS J. Comput. Math. 18 (2015), no. 1, 170–197. MR-3349314
  * [8] N. Bruin, _The arithmetic of Prym varieties in genus 3_ , Compos. Math. 144 (2008), no. 2, 317–338. MR-2406115
  * [9] N. Bruin and K. Doerksen, _The arithmetic of genus two curves with $(4,4)$-split Jacobians_, Canad. J. Math. 63 (2011), no. 5, 992–1024. MR-2866068
  * [10] R. Cosset, _Factorization with genus 2 curves_ , Math. Comp. 79 (2010), no. 270, 1191–1208. MR-2600562
  * [11] D. Cox, J. Little, and D. O’Shea, _Ideals, varieties, and algorithms._ An introduction to computational algebraic geometry and commutative algebra. Second edition. Undergraduate Texts in Mathematics, Springer-Verlag, New York, 1997. MR-1417938
  * [12] R. Donagi and R. Livné, _The arithmetic-geometric mean and isogenies for curves of higher genus_ , Ann. Scuola Norm. Sup. Pisa Cl. Sci. (4) 28 (1999), no. 2, 323–339. MR-1736231
  * [13] V. Z. Enolski and Y. N. Fedorov, _Algebraic description of jacobians isogeneous to certain Prym varieties with polarization (1,2)_ , Experimental Mathematics, to appear. arXiv:1411.6143
  * [14] D. M. Freeman and T. Satoh, _Constructing pairing-friendly hyperelliptic curves using Weil restriction_ , J. of Number Theory 131 (2011), no. 5, 959–983. MR-2772481
  * [15] G. Frey and E. Kani, _Curves of genus $2$ covering elliptic curves and an arithmetical application_. In: Arithmetic algebraic geometry (Texel, 1989), pp. 153–176, Progr. Math., vol. 89, Birkhäuser Boston, Boston, MA, 1991. MR-1085258
  * [16] I. M. Gelfand, M. M. Kapranov, and A. V. Zelevinsky, _Discriminants, resultants, and multidimensional determinants_ , Mathematics: Theory & Applications, Birkhäuser Boston Inc., Boston, MA, 1994. MR-1264417
  * [17] J. González, J. Guàrdia, and V. Rotger, _Abelian surfaces of ${\rm GL}_{2}$-type as Jacobians of curves_, Acta Arith. 116 (2005), no. 3, 263–287. MR-2114780
  * [18] E. Goursat, _Sur la réduction des intégrales hyperelliptiques_ , Bull. Soc. Math. France 13 (1885), 143–162. MR-1503964
  * [19] E. W. Howe, F. Leprévost, and B. Poonen, _Large torsion subgroups of split Jacobians of curves of genus two or three_ , Forum Math. 12 (2000), no. 3, 315–364. MR-1748483
  * [20] E. Kani, _The number of curves of genus two with elliptic differentials_ , J. Reine Angew. Math. 485 (1997), 93–121. MR-1442190
  * [21] F. Kötter, _Ueber die Bewegung eines festen Körpers in einer Flüssigkeit_ , J. Reine Angew. Math. 109 (1892), 51–81 and 89–111. MR-1580255 and MR-1580257
  * [22] R. M. Kuhn, _Curves of genus $2$ with split Jacobian_, Trans. Amer. Math. Soc. 307 (1988), no. 1, 41–49. MR-0936803
  * [23] A. Kumar, _Hilbert modular surfaces for square discriminants and elliptic subfields of genus 2 function fields_ , Res. Math. Sci. 2 (2015), Art. 24, 46 pp. MR-3427148
  * [24] A. Levin, _Siegel’s theorem and the Shafarevich conjecture_ , J. Théor. Nombres Bordeaux 24 (2012), no. 3, 705–727. MR-3010636
  * [25] K. Magaard, T. Shaska, and H. Völklein, _Genus 2 curves that admit a degree 5 map to an elliptic curve_ , Forum Math. 21 (2009), no. 3, 547–566. MR-2526800
  * [26] D. Mumford, _Prym varieties. I_. In: Contributions to analysis (a collection of papers dedicated to Lipman Bers), pp. 325–350. Academic Press, New York, 1974. MR-0379510
  * [27] D. Mumford, _The red book of varieties and schemes_. Second, expanded edition. Includes the Michigan lectures (1974) on curves and their Jacobians. With contributions by Enrico Arbarello. Lecture Notes in Mathematics, vol. 1358, Springer-Verlag, Berlin, 1999. MR-1748380
  * [28] Y.-D. Shieh, _Point counting on non-hyperelliptic genus 3 curves with automorphism group $\mathbb{Z}/2\mathbb{Z}$ using Monsky-Washnitzer cohomology._ In: Algorithmic arithmetic, geometry, and coding theory, pp. 173–189, Contemp. Math., vol. 637, Amer. Math. Soc., Providence, RI, 2015. MR-3364448