Simulating Structural Plasticity of the Brain more Scalable than Expected

2025-05-03 0 0 247.19KB 8 页 10玖币

侵权投诉

Simulating Structural Plasticity of the Brain more

Scalable than Expected?

Fabian Czappa1,∗

, Alexander Geiß1, Felix Wolf1

Abstract

Structural plasticity of the brain describes the creation of new and the deletion

of old synapses over time. Rinke et al. (JPDC 2018) introduced a scalable

algorithm that simulates structural plasticity for up to one billion neurons on

current hardware using a variant of the Barnes–Hut algorithm. They demonstrate

good scalability and prove a runtime complexity of

(

nlog2n

). In this comment

paper, we show that with careful consideration of the algorithm and a rigorous

proof, the theoretical runtime can even be classiﬁed as O(nlog n).

Introduction

In a recent publication [

], the authors presented an algorithm that allows

fast and scalable simulations of structural plasticity in the human brain. They

achieved this by formulating the Model of Structural Plasticity (MSP) [

] as an

N-body problem and adapting the Barnes–Hut-algorithm [1].

In this comment paper, we want to improve the calculations of the runtime

complexity from

(

n·log2

(

)) to

(

n·log

(

)) by revisiting the theoretical

considerations for the same algorithm as in [

]. We summarize the algorithm

Adapted Barnes–Hut-Algorithm

before calculating the sharp runtime

bound in

A Sharp Runtime Bound

. Then we derive the

Complexity in

the Parallel Case

and compare it to the empirical performance models of [

Adapted Barnes–Hut-Algorithm

The Barnes–Hut-algorithm allows approximating the force that

bodies

exert on another body in

(

log

(

)) time. It achieves this by building an octree

?DOI of published journal article: 10.1016/j.jpdc.2022.09.001.

2022. This manuscript version is made available under the CC-BY-NC-ND 4.0 license

https://creativecommons.org/licenses/by-nc-nd/4.0/.

∗Corresponding author

Email addresses: fabian.czappa@tu-darmstadt.de (Fabian Czappa),

alexander.geiss1@tu-darmstadt.de (Alexander Geiß), felix.wolf@tu-darmstadt.de (Felix

Wolf)

Laboratory for Parallel Programming, Department of Computer Science, Technical Uni-

versity of Darmstadt, Germany

Preprint submitted to Elsevier June 2022

arXiv:2210.05267v2 [cs.DC] 2 Nov 2022

(in 3D; a quadtree in 2D) of all bodies, dividing the simulation space into

halves along each axis until at most one body is left per sub-space. Then, the

algorithm allows approximating the force of a whole subspace by the root of the

corresponding subtree whenever the subspace is far away for its size.

The position of a virtual body (an inner node of the tree) is the weighted

average of the positions of the approximated real bodies (we call that the

centroid ), weighted by a body-dependent scalar (in our case, the number of

vacant synaptic elements). Whenever this virtual body is used, its weight is the

sum of the weights of all approximated bodies. The approximation is valid if

the maximum length of a subspace

divided by the distance from the target to

the virtual body dis smaller than a previously ﬁxed θ > 0.

If a neuron wants to create a new synapse, it searches for another neuron

with a vacant synaptic element of the opposite type (a synapse is always formed

from an axon to a dendrite). It does so by checking the Acceptance Criterion

(AC)

l/d < θ

for the root of the octree, unpacking a virtual neuron if it does not

satisfy the AC, and rechecking its children. Once a neuron establishes a list of

potential partners (actual neurons or virtual neurons that are far enough away),

it uses this list to calculate the attracting forces and picks a partner accordingly.

If this partner is a virtual neuron, the searching neuron needs to unpack it and

use the Barnes–Hut-algorithm again, this time starting from the virtual neuron

instead of the root of the octree.

If the octree is balanced, its height is

(

log

(

)) for

neurons, and in the

worst case, there must be

(

log

(

)) applications of the Barnes–Hut-algorithm

per neuron searching a partner. This is the case if a neuron repeatedly picks a

virtual neuron as close as possible to the respective root. Overall, the runtime

is in

(

n·log

(

)

·log

(

)), i.e., every neuron (

) has to perform

(

log

(

))

Barnes–Hut-algorithms, which all have complexity O(log(n)).

In the parallel version of this algorithm, each MPI rank is responsible for a

ﬁxed number of neurons. A rank gets assigned a sub-space in which it places all

its neurons and for which it builds such an octree (enforcing a suitable number

of MPI ranks to avoid boundary issues). In every update step, a rank updates

the centroids and the numbers of vacant elements in its local sub-tree. Then,

all ranks exchange the roots of their sub-trees and construct the common upper

portion of the octree. Whenever a rank now needs access to the children of

another rank’s node (e.g., when the AC is not satisﬁed for the branch node or it

picked a remote node later on), it downloads the children and inserts them into

its own tree. These downloaded nodes are discarded at the end of the update

step so that the newly calculated values can be used in the next update step.

Algorithm 1 shows the pseudo-code for ﬁnding targets in this parallel version.

A Sharp Runtime Bound

In the previous publication, the authors advised setting

θ≤

/√3

. This way,

a subspace that contains the searching neuron is always unpacked because it

never satisﬁes the Acceptance Criterion (AC). This precaution prevents autapses

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

SimulatingStructuralPlasticityoftheBrainmoreScalablethanExpected?FabianCzappa1,,AlexanderGei1,FelixWolf1AbstractStructuralplasticityofthebraindescribesthecreationofnewandthedeletionofoldsynapsesovertime.Rinkeetal.(JPDC2018)introducedascalablealgorithmthatsimulatesstructuralplasticityforuptoonebill...

展开>> 收起<<

Simulating Structural Plasticity of the Brain more Scalable than Expected.pdf

共8页,预览2页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Simulating Structural Plasticity of the Brain more Scalable than Expected

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: