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
O
(
nlog2n
). In this comment
paper, we show that with careful consideration of the algorithm and a rigorous
proof, the theoretical runtime can even be classified as O(nlog n).
Introduction
In a recent publication [
3
], 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) [
2
] 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
O
(
n·log2
(
n
)) to
O
(
n·log
(
n
)) by revisiting the theoretical
considerations for the same algorithm as in [
3
]. We summarize the algorithm
in
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 [
3
].
Adapted Barnes–Hut-Algorithm
The Barnes–Hut-algorithm allows approximating the force that
N
bodies
exert on another body in
O
(
log
(
n
)) 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)
1
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
l
divided by the distance from the target to
the virtual body dis smaller than a previously fixed θ > 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
O
(
log
(
n
)) for
n
neurons, and in the
worst case, there must be
O
(
log
(
n
)) 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
O
(
n·log
(
n
)
·log
(
n
)), i.e., every neuron (
n
) has to perform
O
(
log
(
n
))
Barnes–Hut-algorithms, which all have complexity O(log(n)).
In the parallel version of this algorithm, each MPI rank is responsible for a
fixed 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 satisfied 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 finding targets in this parallel version.
A Sharp Runtime Bound
In the previous publication, the authors advised setting
θ≤
1
/√3
. This way,
a subspace that contains the searching neuron is always unpacked because it
never satisfies the Acceptance Criterion (AC). This precaution prevents autapses
2
摘要：

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

展开>> 收起<<
Simulating Structural Plasticity of the Brain more Scalable than Expected.pdf

共8页,预览2页

还剩页未读， 继续阅读

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

相关推荐

更多
立即下载
分类：图书资源 价格：10玖币 属性：8 页 大小：247.19KB 格式：PDF 时间：2025-05-03

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务

作者详情

相关内容

更多

热门标签

人际关系 动力学连接体 力的合成 配电装置 高考理综 全宋诗作者索引 公务员考试
/ 8
评分 收藏
分享
立即下载
客服
关注