日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

Supporting Multiple Inheritance in an
Object-Oriented DSL for GPGPU by Class
Hierarchy Transformation
Fathul Asrar Alfansuri, Hidehiko Masuhara,Luthfan Lubis, Youyou Cong
Object-support in GPGPU domain speciﬁc languages (DSL) enables highly parallel object-oriented programming on GPUs. This paper improves object-support in Sanajeh, a Python DSL for GPGPU, by adding a
multiple inheritance feature. Existing Sanajeh is restricted to single inheritance, which has limited ﬂexibility. This restriction is due to its backend library which is not trivial to be extended. The limitation makes
it diﬃcult for Sanajeh to represent multiple classes that share common behaviors but belong to diﬀerent
class hierarchies. Our approach transforms a multiple inheritance class hierarchy into a single inheritanceclass hierarchy through mixin linearization, class duplication and wrapper functions at the Python level. We
evaluate this work by rewriting agent-based modeling simulation program. We then compare the originaland rewritten version with respect to their execution result and code eﬀectiveness. The execution time is2% slower than the original code.

This restriction is due to the DSL using a custom

1 Introduction

framework for CUDA/C++ called DynaSOAr [8],Ease-of-use for General Programming for Graphi-

which only supports single inheritance.

cal Processing Unit (GPGPU) is an active researchThis study describes an implementation of mul-

topic in parallel programming. One approach totiple inheritance for Sanajeh. The multiple inher-

make GPGPU easier to use is to implement Object-itance in this study is a mixin-like inheritance [2],Oriented Programming (OOP).

which diﬀers from Python’s own multiple inheri-

One feature of OOP is multiple inheritance. Thisfeature oﬀers ﬂexibility an code reuse.

tance. The implementation is done through code

Due totransformation that converts a multiple inheritanceits complexity however, it is interpreted and im-class hierarchy to a single inheritance class hier-plemented diﬀerently for each of OOP-based lan-archy. The transformation algorithm is similar toguages.

hierarchy linearization in mixin.

Sanajeh [3] is a Python DSL GPGPU. While

The rest of the paper is organized as follows.

Python itself supports multiple inheritance, Sana-Section 2 explains about Sanajeh and its back-jeh is restricted to only support single inheritance.

end framework, DynaSOAr. We then discuss theproblem in implementing multiple inheritance on

Fathul Asrar Alfansuri, Hidehiko Masuhara, Luthfan Lubis, Youyou Cong, School of Computing, Department of Mathematical and Computing Science,
Tokyo Institute of Technology.

Sanajeh in Section 3. In Section 4, we describe
the code transformation and its implementation details. Section 5 shows our testing of the transfor-mation, its results, and the discussion. Section 6discuss works related to this study. Finally we con-(a)clude the paper in section 7.

Agent(empty)

Shark(empty)(empty)

Shark

...

...

...

Class Agent, N=8
int age, int pos

2 Background2. 1 Sanajeh and DynaSOAr
Sanajeh is a Python DSL for GPGPU. This DSL(b)utilizes DynaSOAr, a CUDA/C++ framework forGPGPU, as its backend to execute GPU code. Asage[0:7]a result, Sanajeh uses ahead-of-time compilation toClass Shark, N=5
int age, int pos, int hungerCtr

run its programs instead of using interpreter. During compilation, the DSL splits user code into two:pos[0:7](c)host code and device code. Host code remains asPython code, while device code is converted intoage[0:4]

DynaSOAr code and compiled into shared library.

pos[0:4]

hungerCtr[0:4]Upon runtime, Sanajeh uses Python FFI to interact with compiled shared library in order to execute

Figure 1

the GPU code.

(a) Memory heap is split into blocks of ﬁxed

DynaSOAr custom memory layout.

DynaSOAr is a CUDA/C++ framework forsize. (b) Block layout for Class Agent. (c)GPGPU. This framework uses custom memory lay-

Block layout of Class Shark.

out in order to optimize memory coalescing. Theframework also supports dynamic object allocation

2. 3 DynaSOAr fake pointerand deallocation, in which allocated objects are

DynaSOAr enables dynamic allocation and deal-

given a fake pointer to access its members. Dy-locations at runtime. During allocation, this frame-naSOAr only supports single inheritance, which inwork provides fake pointer as reference to the ob-turn limits Sanajeh to also supports single inheri-ject. The fake pointer contains the pointer of thetance only.

block containing the object and the object’s index
within the block. Field access for the object is cal-

2. 2 DynaSOAr memory layout

culated by using these 2 values.

DynaSOAr uses a custom Structure-of-Array

For example, consider the following code:(SoA) memory layout in order to optimize mem-class Agent { int age ; int pos ; };A *a;a - > pos = 10;

ory coalescing. This framework creates a memory
heap which is converted into blocks with ﬁxed size(ﬁgure 1a). Each blocks may only be allocated for

The block that contains class Agent is arranged

one class type, which may vary in size. Therefore,as illustrated in ﬁgure 2. During allocation, object

the block varies in the maximum number of objects

a is assigned into a block with address (*P) and it

it can contain, depending on the size of the class it

is the 4-th object in the block (I). These two infor-

currently designated to (ﬁgure 1b and 1c). Thismation are stored within the object’s fake pointer.

number is known at compile time. Objects stored

Meanwhile, the maximum number of objects (N) iswithin the blocks are arranged in SoA layout.

known at compile time, and obtained as a constant.

*P*a->age*a->pos*P*a->age*a->pos(a)N=8Figure 2

I=4

N=8*Pb

How the block stores member ﬁeldsof object a of class Agent.

I=4*b->age *b->pos *b->hungerCtr(b)Therefore, ﬁeld access of a->pos is then calculated
N=5

as:a - > pos = * P+ N * sizeof ( age )+ I * sizeof ( pos )I=4*c->eggCtr*Pc*c->pos*c->age*c->hungerCtr(c)

3 Problem
It is not trivial to implement multiple inheritancedirectly on DynaSOAr. The diﬃculty comes fromthe fake pointer mechanism described in Section
2. 3. Simply reusing that mechanism to extend intosizeof(Breed)Figure 3

N=4

I=4

Block layouts for (a) Class Agent,(B) Class Shark, and (C) Class NewShark.

multiple inheritance would lead to incorrect result.
On the other hand, recreating another mechanism

Due to the layout similarity between A and B,for the pointer operation could signiﬁcantly makeﬁeld access for b->pos is calculated the same way:

memory access slower.
To illustrate the problem, consider the following
code:class Breed { int eggCtr ; }class Agent { int age ; int pos ; };class Shark : Agent { int hungerCtr ; };class NewShark : Breed , Agent {int hungerCtr ;};Agent * a ; Shark * b ; NewShark * c ;a - > pos = 10;
b - > pos = 11;
c - > pos = 12;

b - > pos = * Pb+ Nb * sizeof ( age )+ Ib * sizeof ( age ) ;From this fact, it can be said that DynaSOAr
supports single inheritance. On the other hand,ﬁeld access for c->pos would be calculated as:c - > pos =+++* Pc
Nc * sizeof ( Breed )Nc * sizeof ( age )Ic * sizeof ( age )Field access of pos leads to ambiguous result.
The calculation of pos for class NewShark objects

The block layout for class A, B, and C is illus-

is diﬀerent from class Agent objects. On the othertrated in ﬁgure 3. As such, ﬁeld access for a->poshand, C is a subtype of A: variable of type C may

is calculated as:

contain either A or C objects at runtime. This leads

a - > pos = * Pa
+ Na * sizeof ( age )+ Ia * sizeof ( age ) ;to a situation where it may be unknown which ﬁeld
access calculation should be used at runtime, thus

parent classes is the primary parent by putting it

Agent
Agent

ﬁrst on the parents list.

Breeding
Behavior

In ﬁgure 5, class Agent is deﬁned as primary par-Breeding
Behavior
Fish

ent for both Fish and Shark (5a). After the removal

Sharkof non-primary parent (BreedBehavior class), theFish

Shark

resulting hierarchy uses only single inheritance(5b).

Figure 4

An example of hierarchytransformation.

(a) Original class hierarchy. (b) Transformed
class hierarchy

4. 2 Reinsert non-primary parents
The next step inserts back removed classes into
the hierarchy (ﬁgure 5c).

produces an incorrect result.

It reinserts the re-moved non-primary parent (BreedBehavior) in be-We also considered to put additional informa-tween the target class (Fish) and its primary parenttion on the fake pointer in order to set a generic(Agent). If the same class would be reinserted intoﬁeld access calculation through dynamic dispatch-

2 diﬀerent child classes, it may be duplicated asing. However, access speed is a top priority: us-necessary.

ing dynamic dispatch to select proper calculation
would lower the ﬁeld access.

A more complex hierarchy may have a class withmore than one non-primary parents (Figure 6). In

4 Hierarchy transformation algorithm

this case, this step linearize the non-primary par-Our solution to support multiple inheritance isents by creating a chain of parent-child relations

to add hierarchy transformation algorithm before

between them (this process also known as mixin

Sanajeh’s own compilation process. The algorithmlinearization). This chain is then inserted in be-transforms user code which has multiple inheri-

tween the target class and its primary parent.

tance hierarchy into intermediate code which uses

After this step, we obtain a linearized single in-

only single inheritance hierarchy (Figure 4). The

heritance hierarchy, with possible duplicate classes.

intermediate code is then further compiled by existing Sanajeh implementation.

4. 3 Resolve duplicated classes

The transformation algorithm takes the following

This step attempts to merge duplicated classes

4 steps: remove non-primary parents, reinsert non-to simplify the hierarchy. Duplicated classes areprimary parents, resolve duplicated classes, andmerged if both has the same parent. In our simple

make super calls explicit. The algorithm is illus-example, the BreedBehavior class which got dupli-trated in ﬁgure 5.

cated in previous step is able to be merged (ﬁgure5d).

4. 1 Remove non-primary parents

There are some hierarchies where the duplicatedThe ﬁrst step removes non-primary parents fromclass cannot be merged (ﬁgure 7a). Both Breed-

the given class hierarchy. A primary parent of a

Behavior classes cannot be merged since they doclass is the parent which has the most priority of

not have a common parent. Furthermore, there arepreserving its relationship. Users can think of pri-two cases within this type of hierarchy, based onmary parent as the parent that the inheriting class

whether the duplicated class is used as variable type

is most resembled to. Users deﬁne which of theor not (e.g. BreedBehavior breed). For the dupli-Agent

Breeding
Behavior

Agent

Breeding
Behavior

FishShark

FishShark

(a)

(b)

Agent

Agent

Breeding
Behavior

Breeding
Behavior

FishShark

Breeding
Behavior

FishShark(c)Figure 5Agent(d)Hierarchy transformation algorithm for a simple multiple inheritance hierarchy.

Fish non-primary parents
Agent
Breeding
Behavior

DiseaseBehavior

Breeding
Behavior

Fish

Fish(a)Figure 6

DiseaseBehavior(b)

Hierarchy transformation where a class (Fish) has more than one non-primary parents(BreedBehavior and DiseaseBehavior).

cated classes that are not used as variable type, weNext, replace variable type of all duplicated classes

can leave them as is (ﬁgure 7b).

(BreedBehavior) into SanajehBaseClass. Finally,

If the duplicated class is used as variable type,set up wrapper functions and up-castings for vari-this is resolved by using common ancestor methodable assignments or accesses to dynamically dis-(ﬁgure 7c). First, create a new super class named

patch into its proper type.

SanajehBaseClass, and make this class as the parent of every class that does not have a parent yet.

Sanajeh
BaseClass

Agent

Breeding
Behavior1
Fish

Breeding
Behavior2

Agent

Breeding
Behavior

Agent

duplicated

Breeding
Behavior2

Breeding
Behavior1

Shark
Fish

Shark
Fish(a)Figure 7(b)Shark(c)Hierarchy transformation where a duplicated class (BreedBehavior) cannot be merged.

4. 4 Make super-calls explicit

mode to record their execution times. Finally, we

The ﬁnal step adjusts super calls to its appro-compare both versions in terms of execution time

priate functions. A class (e.g. Fish) in the modi-and code length.

ﬁed hierarchy (ﬁgure 5d) may have diﬀerent parent

We run the simulation using a machine withcompared to the original hierarchy (ﬁgure 5a). For

12GB memory NVIDIA TITAN Xp GPU. The Wa-

each class that has its parent changed, any super

Tor simulation parameters are 100x100 cell size andcall functions will be replaced into its direct func-

100 steps for each run.
Our test results are as presented in table 1. Thetion reference.

5 Results & Discussion

render mode execution showed that both version
yields expected result. The no-render test showedAspect
Execution time(seconds)
Source code size
(lines of code)
Table 1SingleMultiple

that the multiple inheritance version is 2% slower

Inheritance

Inheritancecompared to single inheritance version.

17.64418.018Sourcecode inspection showed that the multiple inheritance version has more line of code compared to309

330

single inheritance version.
The multiple inheritance version is unexpectedly

Execution results.

slower than the single inheritance version.

Wetake a look at the intermediary code, and we susWe tested our implementation as follows. First,

pect that the dynamic dispatch increases the execu-

we write a benchmark application for DynaSOArtion time. Dynamic dispatch introduces branching,named Wa-Tor in both single inheritance and mul-which is discouraged in GPGPU.

tiple inheritance version. Next, we run both ver-The longer source code is within our expectation.

sions in render mode to check its visual output.

Since Wa-Tor has a small hierarchy, the new classes

After that, we re-run the execution in no-render

introduces code overhead yet is not being reused

optimally. We estimated that if we add more types

mation algorithm according to mixin linearization.

of agent in this simulation, those new agents will

However, in some complex hierarchies, the mod-beneﬁt from code reuse, thus will have smaller code

iﬁed hierarchy may be diﬀerent than the output

length compared to single inheritance version.

of Python’s own C3 linearization. Further studies
may improve this algorithm by utilizing Python’s

6 Related works

built-in linearization to determine the parents of a

There are several projects for expanding GPGPUclass.

into high-level languages that supports OOP. Ikra
[5] is a GPGPU extension for Ruby, in which an-References

other study provides object-support for it [7].

[1] Barik, R., Kaleem, R., Majeti, D., Lewis, B. T.,
Shpeisman, T., Hu, C., Ni, Y., and Adl-Tabatabai,
A.-R.: Eﬃcient mapping of irregular C++ applications to integrated GPUs, Proceedings of Annual
IEEE/ACM International Symposium on Code
Generation and Optimization, 2014, pp. 33–43.
[2] Bracha, G. and Cook, W.: Mixin-based inheritance, ACM Sigplan Notices, Vol. 25, No. 10(1990),
pp. 303–311.
[3] Jizhe, C., Springer, M., Masuhara, H., and Cong,
Y.: Sanajeh: A DSL for GPGPU programming withPython objects.
[4] Klöckner, A., Pinto, N., Lee, Y., Catanzaro,
B., Ivanov, P., and Fasih, A.: PyCUDA and PyOpenCL: A scripting-based approach to GPU runtime code generation, Parallel Computing, Vol. 38,
No. 3(2012), pp. 157–174.
[5] Masuhara, H. and Nishiguchi, Y.: A data-parallel
extension to ruby for GPGPU: toward a framework for implementing domain-speciﬁc optimizations, Proceedings of the 9th ECOOP Workshop onReﬂection, AOP, and Meta-Data for Software Evolution, 2012, pp. 3–6.
[6] Nishino, R. and Loomis, S. H. C.: CuPy: A
NumPy-compatible Library for NVIDIA GPU Calculations, 31st confernce on neural information
processing systems, Vol. 151(2017).
[7] Springer, M. and Masuhara, H.: Object support
in an array-based GPGPU extension for Ruby, Proceedings of the 3rd ACM SIGPLAN International
Workshop on Libraries, Languages, and Compilers
for Array Programming, 2016, pp. 25–31.
[8] Springer, M. and Masuhara, H.: DynaSOAr: aparallel memory allocator for object-oriented programming on GPUs with eﬃcient memory access,arXiv preprint arXiv:1810.11765, (2018).
[9] Tesone, P., Polito, G., Fabresse, L., Bouraqadi,N., and Ducasse, S.: Implementing modular classbased reuse mechanisms on top of a single inheritance VM, Proceedings of the 33rd Annual ACM
Symposium on Applied Computing, 2018, pp. 1030–1037.

In Python, CUPY [6] and PyCUDA [4] allows
GPU utilization.

These two libraries uses stan-dard CUDA implementation, as opposed to Sanajeh which uses DynaSOAr, an optimized CUDA
framework.
Concord [1] is a heterogeneous C++ programming framework for processors with integrated
GPUs designed for general purpose object-orientedprogramming. It enables GPU execution by using
C++, which includes multiple inheritance support.
Concord uses native memory allocation which is not
optimized for better GPU execution.
Modular Class-based Reuse Mechanisms [9] deﬁnes a modular meta-level runtime architecturethat converts several code reuse mechanism into
single inheritance environment. However, this work
is tailored for targeting a Virtual Machine.

7 Conclusion
We presented an implementation of multiple inheritance in Sanajeh, a Python DSL for GPGPU
through hierarchy transformation algorithm. This
support extends Sanajeh’s capabilities for multiple
inheritance ﬂexibilities, such as better code reuse
and maintainability. However, there is a trade-oﬀ
between those advantages and execution times.
One area of improvement is the expected output of our algorithm. We designed the transfor-