Loading [MathJax]/jax/output/SVG/jax.js
  • 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

基于用户重购行为的产品推荐方法

耿杰, 刘春丽, 魏雪梅, 程明月, 袁昆, 李洋, 刘业政

耿杰, 刘春丽, 魏雪梅, 程明月, 袁昆, 李洋, 刘业政. 基于用户重购行为的产品推荐方法[J]. 计算机研究与发展, 2023, 60(8): 1795-1807. DOI: 10.7544/issn1000-1239.202330263
引用本文: 耿杰, 刘春丽, 魏雪梅, 程明月, 袁昆, 李洋, 刘业政. 基于用户重购行为的产品推荐方法[J]. 计算机研究与发展, 2023, 60(8): 1795-1807. DOI: 10.7544/issn1000-1239.202330263
Geng Jie, Liu Chunli, Wei Xuemei, Cheng Mingyue, Yuan Kun, Li Yang, Liu Yezheng. Product Recommendation Method Based on User Repurchase Behavior[J]. Journal of Computer Research and Development, 2023, 60(8): 1795-1807. DOI: 10.7544/issn1000-1239.202330263
Citation: Geng Jie, Liu Chunli, Wei Xuemei, Cheng Mingyue, Yuan Kun, Li Yang, Liu Yezheng. Product Recommendation Method Based on User Repurchase Behavior[J]. Journal of Computer Research and Development, 2023, 60(8): 1795-1807. DOI: 10.7544/issn1000-1239.202330263
耿杰, 刘春丽, 魏雪梅, 程明月, 袁昆, 李洋, 刘业政. 基于用户重购行为的产品推荐方法[J]. 计算机研究与发展, 2023, 60(8): 1795-1807. CSTR: 32373.14.issn1000-1239.202330263
引用本文: 耿杰, 刘春丽, 魏雪梅, 程明月, 袁昆, 李洋, 刘业政. 基于用户重购行为的产品推荐方法[J]. 计算机研究与发展, 2023, 60(8): 1795-1807. CSTR: 32373.14.issn1000-1239.202330263
Geng Jie, Liu Chunli, Wei Xuemei, Cheng Mingyue, Yuan Kun, Li Yang, Liu Yezheng. Product Recommendation Method Based on User Repurchase Behavior[J]. Journal of Computer Research and Development, 2023, 60(8): 1795-1807. CSTR: 32373.14.issn1000-1239.202330263
Citation: Geng Jie, Liu Chunli, Wei Xuemei, Cheng Mingyue, Yuan Kun, Li Yang, Liu Yezheng. Product Recommendation Method Based on User Repurchase Behavior[J]. Journal of Computer Research and Development, 2023, 60(8): 1795-1807. CSTR: 32373.14.issn1000-1239.202330263

基于用户重购行为的产品推荐方法

基金项目: 国家自然科学基金项目(72271084,72071069)
详细信息
    作者简介:

    耿杰: 1993年生. 博士. 主要研究方向为推荐系统、电子商务和数据挖掘

    刘春丽: 1989年生. 博士,讲师,硕士生导师. 主要研究方向为推荐系统、金融科技和数据挖掘

    魏雪梅: 1995年生. 博士. 主要研究方向为推荐系统、社交网络和数据挖掘

    程明月: 1993年生. 博士. 主要研究方向为推荐系统、表示学习和数据挖掘

    袁昆: 1991年生,博士,讲师,硕士生导师. 主要研究方向为推荐系统、商务智能和社交网络分析

    李洋: 1986年生. 博士,助理教授. 主要研究方向为数据挖掘、电子商务新兴技术和社交媒体分析

    刘业政: 1965年生. 博士,教授,博士生导师. 主要研究方向为推荐系统、商务智能和网络空间管理

    通讯作者:

    刘春丽(liuchunli@hfut.edu.cn

  • 中图分类号: TP391

Product Recommendation Method Based on User Repurchase Behavior

Funds: This work was supported by the National Natural Science Foundation of China (72271084, 72071069).
More Information
    Author Bio:

    Geng Jie: born in 1993. PhD. Her main research interests include recommendation system, e-commerce, and data mining

    Liu Chunli: born in 1989. PhD, lecturer, master supervisor. Her main research interests include recommendation system, financial technology, and data mining

    Wei Xuemei: born in 1995. PhD. Her main research interests include recommendation system, social network, and data mining

    Cheng Mingyue: born in 1993. PhD. His main research interests include recommendation system, representation learning, and data mining

    Yuan Kun: born in 1991. PhD, lecturer, master supervisor. His main research interests include recommendation system, business intelligence, and social network analysis

    Li Yang: born in 1986. PhD, assistant professor. His main research interests include data mining, emerging technologies in e-commerce, and social media analysis

    Liu Yezheng: born in 1965. PhD, professor, PhD supervisor. His main research interests include recommendation system, business intelligence, and cyberspace management

  • 摘要:

    重复购买是消费者日常消费决策中的常见现象,考虑用户重购行为对于提升产品个性化推荐准确性至关重要. 然而针对用户重购行为建模和预测的研究工作相对较少,还有很多问题有待解决. 已有推荐技术主要通过深度挖掘产品、用户或时间某一层面信息来进行重购产品推荐,忽略了对多层次信息融合建模方法的研究,同时也忽略了重购推荐结果的可解释性需求. 因此,融合多层次用户偏好信息,构建了具有双层注意力机制的可解释用户重复消费推荐方法. 该方法融合注意力机制和指针生成网络,多层次提取并学习用户重购偏好,同时基于信息处理理论构建S型用户重购动态偏好函数,融合产品流行度信息进行重购产品和新颖产品的混合推荐,提高了模型可解释性和准确性. 真实数据集上的实验结果表明,所提方法在多个性能指标上都优于对比方法, 且学习出的参数具备较好的可解释性. 此外,通过回归分析验证了S型重购动态偏好函数的可信性,进一步增强了理论的可解释性.

    Abstract:

    Repeat purchase is a common phenomenon in daily consumption decisions, and is crucial for improving the accuracy of personalized product recommendations. However, there is limited research on modeling and predicting user repurchase behaviors. Many issues need to be studied. It is notable that most of existing methods only optimize product, basket or time series level information for repurchase recommendation. They not only ignore the modeling of multi-level information fusion, but also ignore the interpretability requirement for repurchase recommendation results. To address the above issues, we propose a novel interpretable repurchase recommendation method based on dual attention mechanism. Our method combines attention mechanism and pointer generation network to extract multi-level user repurchase preference. We also propose an S-type user repurchase dynamic preference function based on information processing theory and integrate product popularity information for mixed recommendation of repurchase and new products, which improves the interpretability and recommendation accuracy of our method. The experimental results on two real world datasets show that our proposed method outperforms baselines in multiple performance indicators and the learned parameters have good interpretability. In addition, regression studies demonstrate the reliability of our S-type repurchase dynamic preference function, which further enhances the interpretability of our method from a theoretical perspective.

  • 目前超级计算机已经迈入E级计算时代,但随着摩尔定律接近失效、颠覆性使能技术迟迟不能实现,超级计算机在访存、通信、能耗等方面仍面临严重的发展瓶颈[1]. 而MPI(message passing interface)集合通信[2]是高性能计算中最重要的通信类型,对整机系统的性能具有重要的影响,提升MPI集合通信性能是突破通信墙的重要手段. 传统的MPI集合通信是基于点到点消息实现的[3-4],随着系统规模的不断扩大,这种实现方式面临越来越严重的性能及可扩展性问题,而硬件集合通信具有性能高、可扩展性好等优点,正受到越来越多的关注[5].

    硬件集合通信中,数据沿聚合树进行规约或广播操作,聚合树的高度、负载均衡性等对集合操作的性能具有至关重要的影响. 本文研究了影响硬件集合通信性能的因素,提出了硬件集合通信开销模型,并以此为基础提出了构建硬件集合通信聚合树的方法. 本文主要贡献包括4个方面:

    1) 提出了硬件集合通信开销模型,能够较精确地计算硬件集合通信的时间开销;

    2) 研究了如何根据消息大小确定聚合树的宽度,从而在网络传输开销与数据计算开销之间取得平衡,以降低集合操作的延迟;

    3) 针对Ⅰ型聚合树,提出了最小高度分层k项聚合树构建方法,相比传统的Ⅰ型聚合树,降低了跨组聚合包的个数,减少了网络拥塞;

    4) 针对Ⅱ型聚合树,提出了最小代价Ⅱ型聚合树构建方法,减少了聚合树使用的交换机数量.

    近年来,网络计算技术发展迅速[6-7]. 网络计算可将数据规约计算、协议处理、数据加解密等原本由处理器承担的计算任务卸载到网络设备中进行,解放了CPU,使CPU可以专注于其他任务的处理. 在高性能计算领域,可利用网络计算提升MPI集合通信性能. 本文将基于网络计算实现的MPI集合通信称为硬件集合通信. MPI集合通信中,Barrier,Bcast,Reduce,Allreduce是应用最广泛的操作,它们均是1对多或多对1的通信模式,适于以硬件集合通信方式实现. 图1显示了Allreduce的实现过程,它利用聚合树完成数据聚合及结果分发操作,该树中叶节点对应通信进程,根节点及中间节点对应交换机. 进行集合通信时,数据先从叶节点向根节点聚合,并在聚合的过程中计算规约结果;到达根节点后再沿反方向将规约结果广播给所有叶节点. 其他集合操作的实现方式与此类似.

    图  1  基于网络计算的Allreduce操作实现过程
    Figure  1.  Implementation phases of Allreduce operation based on in-network-computing

    目前,很多公司推出了面向高性能计算的硬件集合通信技术,如IBM BlueG/Q中的硬件集合通信原语[8-11]、Mellanox的SHARP技术[5, 12-14]、神威互连网络中的硬件集合通信[15]等. 相较于点到点消息实现的集合通信,硬件集合通信的性能有了显著提升. Zimmer等人[16]在Summit系统中利用基准程序对SHARP性能进行了测试,4096个节点规模下集合消息性能至少提升了1倍.

    硬件集合通信除了需要特殊的硬件支持外,还需要网络管理软件的密切配合,以完成聚合树分配、多播路由配置等操作. 其中,聚合树分配是其中最为关键的操作. 现有的硬件集合通信技术在分配聚合树时还存在3个问题:

    1) 缺乏精确的集合通信开销模型,无法更好地指导聚合树构建. 基于α-β模型的软件集合通信开销模型[3]过于简化,而针对特定网络的专用模型又不具备通用性[17],它们均不适用于硬件集合通信.

    2) 构造聚合树时未考虑相互干扰问题. 当系统中存在大量通信域时,需要为每个通信域分配1棵独立的聚合树,以降低各通信域间的相互干扰,而现有的聚合树分配方法未充分考虑到该问题. 例如,SHARP技术中每个作业的所有通信域共享同一棵聚合树[18],这会产生严重的相互干扰. 现有的聚合树构建方法也没有考虑到同一聚合树内不同消息间的相互干扰问题. 例如,传统方法构建出的聚合树会产生较多的跨组通信,使得同一集合操作的不同消息因竞争通信链路而相互干扰.

    3) 未考虑硬件通信资源不够用问题. 网络中用于支持硬件集合通信的资源是有限的,而现有的聚合树构建方法未考虑该问题,导致出现通信资源不够用的情况. 例如,BlueG/Q中每个网络节点最多支持12棵聚合树,在很多情况下,由于聚合树数量不足,无法使用硬件集合通信[11].

    针对上述3个问题,本文研究如何建立硬件集合通信开销模型,以及如何基于该模型高效地构建聚合树.

    定义1. 互连网络. 互连网络定义为有向图I=(N, L),其中N为网络节点集合,L为通信链路集合. 网络节点包括网卡及交换机. 本文假设网卡在I中均是叶节点.

    定义2. 聚合树. 在互连网络I=(N, L)上目标集合MMN)对应的聚合树是一棵树A=(NA, LA),MNAN,其中M是通信域中各进程所在的网卡集合. A中边(μ,υ)的长度定义为Iμυ的距离,也即I中从μυ经过的网络链路数. A不必是I的子树,也即不要求LAL. 另外,M中允许有重复元素,从而使得每个节点上可同时运行多个通信进程. 聚合树还需满足度约束条件,也即每个节点的最大子节点数不能超过硬件阈值.

    定义3. 聚合树高度. 设A=(NA, LA)是互连网络I=(N, L)上目标集合M对应的一棵聚合树,A中从叶节点出发到达根节点所经过的边的最大条数,称为聚合树的高度. 只有1个节点的聚合树高度为0.

    定义4. 聚合树半径. 设A=(NA, LA)是互连网络I=(N, L)上目标集合M对应的一棵聚合树,A中从叶节点出发到根节点所经过边的长度之和的最大值称为聚合树半径. 聚合树半径实际上是从各叶节点出发沿该聚合树依次经过各祖先最终到达根节点时所经过的最大链路条数.

    现有的硬件集合通信技术中,有的仅支持将集合操作卸载到网卡中进行,有的则还可将集合操作卸载到交换机中进行. 根据不同的卸载位置,本文将聚合树分为Ⅰ型聚合树及Ⅱ型聚合树2种类型.

    定义5. Ⅰ型聚合树. 设A=(NA, LA)是互连网络I=(N, L)上目标集合M对应的一棵聚合树,若M = NA,则称A为Ⅰ型聚合树. 该类聚合树中,集合操作均被卸载到网卡中执行,且仅使用进程所在的那些网卡.

    定义6. Ⅱ型聚合树. 设A=(NA, LA)是互连网络I=(N, L)上目标集合M对应的一棵聚合树,T=(NT, LT)是I的一棵子树,MNANTN,且T中叶节点均在M中. 若uNAuA中的父亲p也是uT中的某个祖先,则称A为Ⅱ型聚合树. Ⅱ型聚合树中的集合操作均被卸载到交换机中进行.

    图2显示了Ⅰ型聚合树和Ⅱ型聚合树. 假设有8个进程参与集合通信,每个网卡上1个进程,互连网络的拓扑结构如图2(a)所示;图2(b)是一棵Ⅰ型聚合树,高度为3,半径为12;图2(c)是一棵Ⅱ型聚合树.

    图  2  Ⅰ型聚合树和Ⅱ型聚合树
    Figure  2.  Aggregate trees of type Ⅰ and type Ⅱ

    本文采用式(1)~(4)所示的开销模型,模型中各变量的含义如表1所示. 本文关注于如何降低聚合过程的开销,下面着重对聚合过程开销进行说明.

    表  1  硬件集合通信开销模型中使用的符号
    Table  1.  Symbols Used in the Cost Model of Hardware Supported Collectives
    符号 含义
    Tcoll 集合操作的总时间开销
    Tpost_wr 应用投递1个集合操作描述符的时间
    Tfetch_wr 网卡读取1个集合操作描述符的时间
    Tfetch_data 网卡从内存读取操作数的时间
    Taggregate 聚合过程的时间开销
    Tbcast 广播过程的时间开销
    Twrite_wc 网卡写完成条目及结果到内存的时间
    Tnoise 噪声导致的开销
    S 用户消息大小(不超过2 KB)
    S 聚合包大小
    S 规约数据长度
    β PCIE链路/网络链路带宽
    l 消息经过1条网络链路的时间
    hatree 聚合树高度
    ratree 聚合树半径
    P 进程总数
    k k叉树的宽度或k项树的基
    θ 每个聚合包的匹配处理时间
    γ 单位长度数据的规约计算时间
    δ 任2个进程间单播路由的最大跳步数
    下载: 导出CSV 
    | 显示表格

    Taggregate是聚合过程的时间,其包括聚合包在网络链路上的传输时间,以及在网络节点内的处理时间. 假设聚合树是k叉完全树,聚合树的半径为ratree,则聚合包在网络链路中的传输总时间为ratree×l. 设每个聚合包的匹配处理时间为θ、存储转发时间为Sβ、规约计算时间为S*×γ,则聚合包在网络节点内的处理总时间为hatree×k×(θ+Sβ+S*×γ). 最终得到式(2)所示的聚合时间开销.

    为进一步简化模型,除了假设聚合树是k叉完全树之外,还假设任意2个进程之间单播路由的路径长度相等,均需经过δ条链路,则对Ⅰ型聚合树,hatreelogkPratreeδ×logkP,从而得到式(3)所示的聚合过程开销. 而对Ⅱ型聚合树,hatreelogkPratree0.5δ,从而得到式(4)所示的聚合过程开销.

    Tcoll=Tpost\_wr+Tfetch\_wr+Tfetch\_data+Taggregate+Tbcast+Twrite\_wc+Tnoise, (1)
    Taggregate=ratree×l+hatree×k×(θ+Sβ+S*×γ), (2)
    Taggregate\_IlogkP×[δl+k(θ+Sβ+S*×γ)], (3)
    Taggregate\_II12δl+logkP×k(θ+Sβ+S*×γ). (4)

    本文在新一代神威超级计算机上测试了各类集合消息的延迟,并与开销模型计算出的结果进行对比. 实验环境如图3所示.

    图  3  测试环境使用的2层胖树
    Figure  3.  2-level fat tree used in the test environment

    使用1个超节点进行测试,超节点内共有256个节点,每个节点安装1块消息处理芯片,每块消息处理芯片有2个网络端口,故整个超节点内共有512个网络端口. 这512个网络端口通过一棵2层胖树进行互连. 该胖树共有48台交换机和其中32台叶交换机和16台骨干交换机. 每台交换机的端口数均为40,其中有些端口未被使用. 每台叶交换机有16个端口用于连接消息处理芯片的网络接口,16个端口用于连接骨干交换机.

    分别在不同进程数下测试了各种类型、各种长度集合消息的延迟. 测试方法为:每种类型及长度均测试5000次,每次测试进程均记录集合操作的时间开销,取耗时最长的那个进程的时间开销作为该次集合通信的时间开销,再取这5000个时间开销的中位值作为当前类型、当前长度下集合消息的延迟.

    限于篇幅,本文仅显示了Ⅰ型聚合树的部分测试结果. 不同进程数下,长度为8 B的广播操作的理论计算延迟与实际测试延迟如图4所示;进程数为512时不同长度Bcast消息的理论计算延迟与实际测试延迟如图5所示. 可以看出,Ⅰ型聚合树的理论计算延迟与实际测试延迟最多相差0.5 μs. 这表明本文提出的硬件集合通信开销模型能够较准确地拟合实测延迟.

    图  4  不同进程数下集合操作的实测延迟及理论计算延迟
    Figure  4.  Measured latency and estimated latency of collectives for different count of processes
    图  5  进程数为512时不同消息大小下集合消息的实测延迟及理论计算延迟
    Figure  5.  Measured latency and estimated latency of collectives for different message size when process count is 512

    给定任意P个进程,为它们构造一棵开销最小的Ⅰ型聚合树是非常困难的,因为不但要考虑聚合树宽度、聚合树半径等因素,还要考虑通信与通信重叠、通信与计算重叠、消息间相互干扰等因素的影响,故目前Ⅰ型聚合树均是通过启发式算法进行构造. 本节首先研究如何根据消息类型、消息长度等确定Ⅰ型聚合树的宽度k,然后研究如何快速构造一棵聚合树,使得跨组聚合包的个数尽可能地少,尽量降低消息间的相互干扰.

    聚合过程的时间开销包括聚合包的传输时间以及处理时间. 聚合树的宽度k对聚合过程的时间开销具有重要影响. 直观上看,如果k很小,则聚合树很高,相应地聚合包的传输开销就很大;如果k很大,则每个网卡需要处理的聚合包很多,相应地聚合包的处理开销就很大. 需要研究k对聚合时间开销的影响.

    先看如何选择k才能使式(3)计算出的聚合开销F(k)最小. 记δ×l=αθ+S'β+S×γ=b,定义如式(5)所示的F(k),其导数函数如式(6)所示.

    F(k)=logkP×[δ×l+k×(θ+Sβ+S*×γ)]=logkP×[a+kb], (5)
    F(k)=(lnP)[kb(lnk1)a]kln2k. (6)

    使F(k)取最小值的k记为k,此时的F(k)记为F. 根据式(5)(6),要使F(k)取最小值,需F(k)=0,也即k(lnk1)=ab,而函数f(k)=k(lnk1)是单调递增的. 对不同的集合操作类型及消息长度,ab取值不同,使F(k)取最小值的k也不同. 在本文的实验环境中,对同步、广播操作来说,k = 41时F(k)取最小值.

    很多情况下,选择其他k值时,Fk)与F差别不大. 以同步、广播操作为例,在本文的实验环境中,设P = 512,a = 1.12 μs,b = 0.01 μs,F(k)的曲线如图6所示,可以看出,当24k64时,F(k)相差不大,不超过0.1 μs. 对每种类型、每种长度的集合消息,都可以确定区间[kmin,kmax],使得k[kmin,kmax]时,|F(k)F|ε成立(ε是常数). 本文测试环境中使用的k表2所示(仅显示了部分结果). 可以发现,随着聚合包长度增大,kminkmax均逐渐下降. 对该现象的直观解释是:当聚合包长度较小时,聚合包在网络链路上的传输时间在总聚合时间中占比最大,此时应该采用较大的k,从而使得聚合包在网络链路上的传输尽量并行;而当聚合包长度较大时,聚合包在网卡内的处理时间在总聚合时间中占比最大,此时应采用较小的k,以使更多的网卡参与聚合包的处理.

    图  6  同步、广播操作的F(k)曲线
    Figure  6.  Curve of F(k) for Barrier and Bcast operation
    表  2  测试环境中使用的Ⅰ型聚合树宽度
    Table  2.  Type Ⅰ Aggregate Tree Breadth Used in the Test Environment
    消息类型聚合包长度/Bkminkmax推荐k
    Barrier/Bcast0326432
    Reduce/AllReduce32166332
    Reduce/AllReduce64155332
    Reduce/AllReduce128134016
    Reduce/AllReduce256102816
    Reduce/AllReduce51281916
    Reduce/AllReduce10246128
    Reduce/AllReduce2048588
    下载: 导出CSV 
    | 显示表格

    确定k值后就可以构建聚合树了. 式(3)假设任意2个进程间的单播路由经过的链路数相等,但实际情况要复杂得多. 使用相同的k值构造的2棵聚合树值半径ratree可能不同,导致聚合包的传输开销不同. 带度约束的最小半径聚合树问题是NP难的[19-21],尚未有高效的求解办法. 本文目标不是构造最优聚合树,而是快速构造出一棵满足度约束条件、半径尽可能小、冲突尽可能少的聚合树. 本节首先介绍2种传统的聚合树构建方法.

    定义7. k叉树. k叉树是一棵完全树,除最后一个中间节点外,根节点及其他中间节点都有k个子节点,故k叉树是平衡树,每个中间节点处理的聚合包个数相等.

    k叉树中,按广度优先遍历方式为进程编号,根进程编号为0. 若进程在通信域内的编号为my_rank,则其父节点编号为(my_rank−1)/k,第i个子节点编号为my_rank×k+i(i1).

    由于未考虑网络拓扑结构,在胖树网络[22-23]、蜻蜓网络[24]等具有分组结构的网络中,k叉树会产生大量的组间通信,导致网络拥塞. 16个进程构建聚合树,其网络拓扑如图7 (a)所示,4叉树如图7(b)所示. 粗线表示该聚合包需要经过最顶层的交换机,图7(b)中共有8个聚合包经过最顶层的交换机. 如果最顶层的交换机传输能力不足,则很容易在顶层交换机处形成拥塞. 而图7(c)是另一棵聚合树,其高度、半径均与图7(b)所示聚合树一样,但仅有2个经过顶层交换机的聚合包,因而具有更优的性能.

    图  7  k叉树易产生大量的组间通信
    Figure  7.  k-ary aggregate tree is prone to generate lots of inter-group communication

    定义8. k项树. k项树[25]是一组递归定义的树Tn,其中T0是1个单节点的树;而Tn是由kTn1连接起来构成的树,其中k−1棵Tn1的根节点直接连接到另外那棵Tn1的根节点上. k项树第i层的节点数是(k1)i×Cin,节点总数是kn,高度为n.

    图8分别显示了一棵2项树及一棵4项树. 2项树是特殊的k项树,在软件集合通信中已得到了广泛使用,例如在MPICH中短的Bcast、Reduce均是通过2项树实现的[3];而大于2的k项树目前使用得较少.

    图  8  k项树(k=2, 4)
    Figure  8.  k-nomial tree (k=2, 4)

    k叉树不同,k项树中不同深度的节点拥有不同数量的子节点,其中根节点的子节点数最多,为(k1)×logkP;而随着深度的增加,子节点数越来越少,故k项树是非平衡树.

    由于k叉树是平衡树,k叉树中上层节点要等待下层节点处理完毕之后才开始处理聚合包,故上层节点会存在空等待现象. 而k项树是非平衡树,位于不同层的节点可以并发处理聚合包,不存在空等待现象.

    k项树中,按深度优先遍历方式为进程编号. 进程编号用k进制表示为kn1k2,k1,k0,其中最低位共有i个0(0in),则第i个位置0即可得到其父节点编号,从最低的i位中任选一位置为1,2,,k1,则得到其子节点的编号最多有i×k1)个子节点.

    每个进程调用算法1所示的build_k_nomial_tree函数计算parent_rankchildren_cnt. 与k叉树一样,k项树也会产生很多跨组通信.

    算法1. build_k_nomial_tree.

    输入:本进程编号 my_rank,基数k,进程总数P

    输出:父节点parent_rank,子节点数children_cnt, 子节点列表children[].

    mask=1,children_cnt=0;

    ② while(mask<P

    ③  if(my_rank%(k×mask)) then

    ④   parent_rank=my_rank/(k×mask)× (k×mask)

    ⑤    break;

    ⑥  end if

    ⑦  mask=mask×k

    ⑧ end while

    mask=mask/k

    ⑩ while(mask>0) do

    ⑪  for (r=1;r<kr++)

    ⑫    child=my_rank+mask×r

    ⑬    if (child < P) then

    ⑭     children[children_cnt]=child

    ⑮     children_cnt+=1;

    ⑯    end if

    ⑰   end for

    ⑱   mask=mask/k

    ⑲ end while

    ⑳ 返回parent_rankchildren_cntchildren.

    传统的聚合树构建方法未考虑网络拓扑结构,容易产生较多的组间通信,从而造成网络拥塞. 为解决此问题,本文提出了分层k项树构建方法.

    分层思想是优化集合通信的一种重要策略[26-29],该策略利用了不同的层具有不同数据传输性能的特点,将同一层内的进程组织成组,使尽可能多的通信在组内完成,以降低层间通信、提升集合消息性能.

    在构建Ⅰ型聚合树时,利用分层思想也可以降低聚合过程的时间开销. Zhao等人[25]提出了一种简单方法:先将进程分为不同的组,并为每个组单独构建一棵k项树;然后将各组的首进程组成一个新的组,并创建一棵k项树,从而将所有组连接起来形成一棵更大的k项树. 进行聚合操作时,同一个组内的进程会先聚合到本组的首进程,首进程再聚合到更高层的首进程,从而大大减少组间通信. 但该方法产生的k项树可能具有较大的高度. 图9举了一个例子:通信域内共有14个进程,依图案分属4个不同的组. 当k = 2时,构建的聚合树如图9(a)所示,其高度为4. 实际上,可以使某个组的首进程连接到另一个组的非首进程下,从而使得聚合树更加平衡,以降低聚合树的高度. 图9(b)即是一棵更优的聚合树,其高度为3. 本文的目标是在最小化组间通信的同时使聚合树高度最低.

    图  9  具有分层结构的聚合树
    Figure  9.  Aggregate tree with hierarchical structure

    本文将具有相同通信特性的一组进程称为一个进程组. 例如,位于同一节点内的多个进程,以及位于同一交换机内的多个进程等,均可构成一个进程组. 进程组可以嵌套,从而使得一个进程组可包含多个子进程组,最终构成1个层次结构.

    进程组由如图10所示的数据结构定义. 每个进程组都对应一棵k项树,按深度优先方式为k项树内的节点编号. 进程被映射到k项树的某个节点上,树中有些节点可能无映射进程. 该数据结构中,cntk项树的节点数,它必须是k的幂;ranks_idk项树内各节点对应的进程号,nodes_id是各进程对应的k项树节点号;sub_groups定义了属于该进程组的子进程组,共有sub_grp_cnt个子进程组.

    图  10  进程组的数据结构
    Figure  10.  The data structure of the process group

    下面探讨最小高度分层k项Ⅰ型聚合树问题. 给定m个互不相交的进程组g0,g1,,gm1g是满足2个条件的进程组:1)g包含g0,g1,,gm1的所有进程;2)g对应的k项树中,除首进程外其余进程的父节点均位于gi内;3)g对应的k项树中,每个节点的儿子数不超过硬件限制. 该问题为从中找出具有最小高度的进程组g,从而为进程组g0,g1,,gm1构建一棵高度最小的分层k项Ⅰ型聚合树. 进程组gi(0i<m)内嵌套的子进程组也需满足条件2.

    g0i是进程组gi首进程的进程号,根据k项树的性质,条件2等价于g.nodes[g0i]%(gi.cnt)=0且对gi内每个进程gjig.nodes[gji]/(gi.cnt)=g.nodes[g0i]/(gi.cnt),也即进程g0i被映射到某个编号为gi.cnt倍数的聚合树节点内,其余进程依次映射到后续节点内.

    给定m个进程组g0,g1,,gm1,且每个gi均已构建好各自的k项树之后,即完成了ranks的设置,采用算法2为这些进程组构建一棵更大的k项聚合树. 算法2采用贪心策略,每次找出2个最大的进程组g0g1,然后在g0的空闲子树内寻找能够容纳g1的位置. 如果找不到这样的位置,则将g0的聚合树高度加1,即cnt变为原来的k倍,从而使g0内有足够的空余位置容纳g1. 该过程持续下去,直到最终只剩1个进程组为止. 算法2行⑤代码用于为g[i]寻找可用的位置,仅需检查分块的第1个位置是否可用即可判断整个分块是否可用. 行⑫~⑭代码用于将g[i]ranks映射表拷贝到新的聚合树中.

    算法2. merge_groups.

    输入:子进程组列表g[]及列表长度m,基数k,父 进程组parent

    输出:无.

    ① 将g[0],g[1],,g[m1]按照cnt字段由大到 小的顺序排列;

    parent.cnt=g[0].cnt

    ③ for(i=0;i<m;++i

    ④  for(j=0;j<parent.cntj+=g[i].cnt

    ⑤   if(parent.ranks[j]==1)then

    ⑥    break;

    ⑦   end if

    ⑧  end for

    ⑨  if(jparent.cnt) then

    ⑩   parent.cnt=pareng×k

    ⑪  end if

    ⑫  for(x=0;x<g[i].cnt;++x

    ⑬   parent.ranks[j+x]g[i].ranks[x]

    ⑭  end for

    ⑮ end for

    采用数学归纳法可证明算法2所产生的k项树是高度最小的分层k项Ⅰ型聚合树,限于篇幅,不再赘述证明过程.

    算法3以递归方式为每个层次建立进程到聚合树节点的映射关系. 算法4根据拓扑信息建立分层的k项树. build_hierarchical_tree建立的聚合树中,每个组的进程均位于同一子树内,从而保证除该组的首进程外其余进程均向本组内的进程发送聚合包,故跨组聚合包的个数相比传统聚合树构建方法减少了. 在使用算法4时,需要选择合适的k,以保证聚合树内每个节点的儿子数不超过硬件限制.

    算法3. build_rank_mapping.

    输入:进程组g

    输出:无.

    ① if(g.sub_grp_cnt==0

    ②  return;

    ③ end if

    ④ for(i=0;i<g.sub_grp_cnt;++i

    ⑤  build_rank_mapping.sub_groups[i]);

    ⑥ end for

    merge_groupsg.sub_groups, g.sub_grp_cnt, k, g).

    算法4. build_hierarchical_tree.

    输入:本进程编号my_rank,基数k,进程总数P

    输出:父节点parent_rank,子节点数children_cnt.

    ① 根据网络拓扑信息构建进程组信息,其中 底层的组其sub_grp_cnt = 0,ranks填充为该 组内各进程的rank号,其他层的组需填充 sub_groups,最高层的组记为g

    build_rank_mappingg)

    ③ 遍历g.ranks找到my_rank在该数组内的下标 node_id

    ④调用build_k_nomial_treenode_id, k, g.cnt)获得 parent_node_id、子节点列表children及列 表长度cnt

    parent_rank=g.ranks[parent_node_id]

    children_cnt=0;

    ⑦ for (i=0;i<cnti++)

    ⑧  if (g.ranks[children[i]]1) then

    ⑨   children_cnt+=1;

    ⑩  end if

    ⑪ end for

    ⑫ 返回parent_rankchildren_cnt.

    本节研究构造Ⅱ型聚合树的方法. 构造Ⅱ型聚合树时需要综合考虑网络拓扑、进程位置等因素. 另外,在每个交换机内,每棵Ⅱ型聚合树都占用1个聚合树条目,而硬件支持的聚合树条目是有限的,故创建Ⅱ型聚合树时,还需要考虑是否有可用的聚合树条目.

    构造Ⅱ型聚合树时要考虑3个目标:1)最小化聚合树的半径,以降低集合操作延迟;2)尽量让不同的聚合树分布到不同链路上,以降低聚合树间的相互干扰;3)使用尽可能少的聚合树条目,以支持创建更多的Ⅱ型聚合树.

    本文分2个步骤构造Ⅱ型聚合树. 1)选择1个交换机作为树根,并构造1棵生成树(称为物理树);2)对物理树进行裁剪,去掉不需要的交换机.

    定义9. 物理树. 设M是某通信域内进程所在的网卡集合,T=(NT, LT)是互连网络I=(N, L)的一棵子树,若T满足2个条件,则称T是关于M的物理树:

    1)MNT

    2)T的叶节点除M中网卡之外,不包含任何其他网卡及交换机.

    定义10. 由物理树推导出的Ⅱ型聚合树. 设K是交换机节点的度约束函数,给定互连网络I=(N, L)上一棵关于M的物理树T=(NT, LT),由物理树T导出的Ⅱ型聚合树是满足2个条件的树A=(NA, LA):

    1)MNANT

    2)若uNAuA中的父亲p也是uT中的某个祖先;

    3)A中每个交换机sw的子节点数不大于度约束Ksw),其中Ksw)大于swT中的子节点数.

    实际上,由物理树T导出的Ⅱ型聚合树A可看成是将T中某些节点提升位置而得到的(仅能提升为其祖先的儿子).

    定义11. Ⅱ型聚合树的代价. 设A=(NA, LA)是互连网络I=(N, L)上目标集合M对应的一棵Ⅱ型聚合树,A中交换机的个数称为该Ⅱ型聚合树的代价,记为costA).

    树根的位置决定了聚合树的半径,应该选择到通信域内各进程最大跳步数最小的交换机作为树根.

    本文采用集中式方法构建物理树. 在该方法中,由集中式的网络管理软件选择树根并构建物理树. 网络管理软件维护了网络的状态信息,包括交换机内空闲的聚合树条目数、网络链路的负载情况等. 网络管理软件可根据这些信息选择一个交换机作为树根.

    该方法具体过程为:先计算出每个交换机到通信域组内各进程的最小跳步数,据此找到所有的备选树根. 然后根据备选树根的负载情况对备选树根进行排序,优先使用负载低的树根. 选择好一个树根后,就可以构造一棵物理树,使得每个进程到树根的跳步数最少. 然后检查该物理树的每个交换机是否有空闲的聚合树条目可用. 若每个交换机都有空闲的聚合树条目,则返回该物理树;若失败,则尝试下一个树根.

    由物理树导出的最小代价Ⅱ型聚合树问题. 给定互连网络I=(N, L)上一棵关于M的物理树T=(NT, LT)及度约束函数K,在由物理树T导出的Ⅱ型聚合树中求代价最小的聚合树A.

    本文利用算法5所示的函数创建最小代价Ⅱ型聚合树. 可以证明算法5产生的聚合树A是由物理树T导出的最小代价Ⅱ型聚合树. 限于篇幅,证明不再赘述.

    算法5. build_minimum_type_Ⅱ_tree.

    输入:物理树T=(NT, LT),度约束函数K

    输出:聚合树A=(NA, LA).

    ①记T的根节点为r,若r不是交换机,则返回仅 包含节点r的聚合树;

    ②否则,对r的每个子节点si,记以si为根的子 树为Ti,调用build_minimum_type_Ⅱ_treeTi,K)产生由物理树Ti导出的最小代价Ⅱ 型聚合树Ai

    ③若r仅有1个子节点T1,则返回该子节点对应 的最小代价Ⅱ型聚合树A1

    ④否则,构造一棵树A=(NA, LA),r为根节点,各 Ai为子树;

    ⑤若Ar的子节点数小于r的度约束K(r),则

    ⑥  从所有Ai中找到一个最小的叶交换机L(叶 交换机是指所有子节点均是网卡的交换 机,最小是指子节点数最小);

    ⑦  从L中任选一进程p,使p成为r的儿子;

    ⑧  若L删掉p后仅剩1个儿子q,则将q设为 q祖父的儿子并删掉L

    ⑨  重复过程⑥~⑧,直到r的子节点数等于 K(r)为止;

    ⑩返回A.

    图11(a)显示了一棵物理树,该树中共有16个进程,使用了13个交换机,每个交换机的度约束均为5;其导出的最小代价Ⅱ型聚合树如图11(b)所示,仅使用了4个交换机.

    图  11  一棵物理树及其导出的最小代价Ⅱ型聚合树
    Figure  11.  A physical tree and its reduced minimum cost type Ⅱ aggregate tree

    在性能方面,Ⅰ型聚合树与Ⅱ型聚合树各有优势. 对长度较小的集合操作,聚合包的传输时间占主导,而Ⅱ型聚合树中聚合包传输路径较短,故延迟比Ⅰ型聚合树低. 对长度较大的集合操作,规约计算时间占主导,Ⅰ型聚合树可以将规约计算分布到大量网卡中并发进行,故延迟较小. 创建通信域时,需要综合考虑各方面因素,选择使用Ⅰ型聚合树还是Ⅱ型聚合树.

    为简化分析,假设Ⅱ型聚合树是标准的d叉树,记δ×l=αθ+Sβ+S×γ=b,则Ⅰ型、Ⅱ型聚合树的时间开销分别如式(7)(8)所示. 为简化讨论,仅考虑S=S=S的情况.

    Taggregate\_I(a+kb)logkP, (7)
    Taggregate\_IIa2+dblogdP. (8)

    定义如式(9)所示的函数F(d,k,P,S)

    F(d,k,P,S)=Taggregate\_ITaggregate\_II=(logkP0.5)a+(klogkPdlogdP)b, (9)
    FP=1P(a+kblnkdblnd), (10)
     FS=(1β+γ)(klogkPdlogdP). (11)

    可以根据式(9)~(11)分析F(d,k,P,S)的变化趋势,并据此构造一张静态映射表. 给定集合操作类型及消息长度后,通过查表即可快速确定聚合树类型及宽度. 表3列出了本文实验环境中如何根据聚合包长度来选择使用Ⅰ型聚合树还是Ⅱ型聚合树. 当申请不到创建Ⅱ型聚合树所需的通信资源时,需要回退到Ⅰ型聚合树.

    表  3  聚合树选择方法
    Table  3.  Method to Select Aggregate Tree
    d 聚合包长度/B 聚合树类型 k
    16 (0, 2 048] Ⅱ 型 16
    64 [0, 323] Ⅱ 型 64
    (323, 512] Ⅰ 型 16
    (512, 2 048] Ⅰ 型 8
    不能创建Ⅱ
    型聚合树时
    [0, 64] Ⅰ 型 32
    (64, 512] Ⅰ 型 16
    (512, 2 048] Ⅰ 型 8
    下载: 导出CSV 
    | 显示表格

    本节将在新一代神威超级计算机中对聚合树性能进行测试.

    首先测试不同的Ⅰ型聚合树集合消息的延迟. 对同步、广播、8B长度的规约操作而言,选择k = 32可以获得更好的性能,故分别构造了32叉树、32项树、分层32项树. 使用1个超节点进行测试,每个节点运行2个进程,每个进程使用1个网络端口,这2个端口间的通信不需要经过网络链路. 分别在2种场景下进行测试.

    在2层标准胖树中进行测试. 分层32项树使用了3个层次,首先将位于同一节点的2个进程组成1个组,这2个进程间的通信不需要经过网络链路;然后将位于同一交换机内的16个进程组成1个组,该组内的进程通信时仅需经过2条链路;最后将位于同一超节点内的所有进程组成1个组,该组内的进程通信时需经过4条链路.

    图12显示了Bcast-8B,Bcast-2KB这2种集合操作的测试结果. 可以看出:1)大部分情况下32叉树、32项树几乎具有相同的延迟;2)大部分情况下,分层32项树的延迟低32叉树、32项树约0.6 μs. 分层32项树延迟低的原因是:它先把位于同一节点内的2个进程组成1个组,而这2个进程间通信不需要经过网络链路,故延迟较低. 需要指出的是,进程数较少时分层32项树的延迟反而高于另外2种聚合树,原因是此时的分层32项树的高度大于32叉树、32项树;随着进程数的增多,这3种聚合树将具有相同的树高.

    图  12  标准胖树拓扑中不同进程数下3种聚合树的消息延迟
    Figure  12.  Messages latency of three types of aggregate trees for different count of processes in standard fat-tree topology

    不同消息长度时3种构造方法下的聚合树的性能如图13所示. 测试时使用了512个进程,每个进程使用1个网络端口. 测试结果与图12的测试结果一致,即32叉树和32项树的性能相当,而分层32项树的延迟明显低于32叉树和32项树.

    图  13  标准胖树拓扑中不同消息长度下3种聚合树的消息延迟
    Figure  13.  Messages latency of three types of aggregate trees for different message sizes in standard fat-tree topology

    使用如图14所示的裁剪胖树进行测试. 该拓扑中,同一交换机内的不同网络端口向其他交换机内的网络端口发消息时会共享一条通信链路. 测试时还在网络中加入了网络噪声,该噪声消耗约80%的网络带宽.

    图  14  测试使用的2层裁剪胖树示意图
    Figure  14.  Illustration of two-layer pruned fat-tree used in the test

    分别测试不同进程数时3种方法构建的聚合树的性能,并将之与标准胖树下的测试结果进行了对比,结果如图15所示. 可以看出,加入网络噪声后,3种构建方法的集合消息延迟相比标准胖树下有显著增大. 其中32叉树增幅最大,分层32项树增幅最小.

    图  15  裁剪胖树拓扑下有干扰时集合通信消息延迟
    Figure  15.  Collective messages latency in pruned fat-tree topology with inference

    图16显示了进程数为512时,3种方法构建的聚合树中跨组聚合包的数量,其中每条实线上的数字表示该实线所连接的2个交换机间的聚合包个数. 在32叉树中,大量聚合包发送到1号交换机的不同进程内,故每个集合操作中,0号交换机与1号交换机间链路上需传输496个聚合包,从而产生严重的链路竞争.

    图  16  裁剪胖树下3种聚合树构建方法的跨组聚合包
    Figure  16.  Inter-group aggregation packets of three types of aggregate trees constructed methods in pruned fat-tree

    表4显示了不同进程数时3种聚合树下Bcast-8 B 的延迟对比,可以看出,在存在噪声干扰的情况下,分层32项树的延迟相比传统的聚合树构建方法下降了24%~89%. 这表明,相比另外2种聚合树构建方法,分层32项树具有更少的跨组聚合包,因而存在带宽竞争的情况下可以显著降低集合消息的延迟.

    表  4  裁剪胖树拓扑下有干扰时不同进程数下Bcast-8B延迟
    Table  4.  Bcast-8B Latency for Different Count of Processes in Pruned Fat-tree Topology with Inference
    进程数 32叉树下
    延迟/μs
    32项树下
    延迟/μs
    分层32项树
    下延迟/μs
    64 19.92(↓39%) 17.79(↓32%) 12.11
    128 25.11(↓49%) 18.58(↓31%) 12.75
    192 35.75(↓64%) 18.54(↓31%) 12.73
    256 42.87(↓70%) 18.62(↓32%) 12.75
    320 71.81(↓82%) 18.86(↓32%) 12.83
    384 97.33(↓86%) 18.94(↓30%) 13.33
    448 115.82(↓87%) 18.80(↓26%) 13.94
    512 136.60(↓89%) 19.48(↓24%) 14.89
    注:括号内的百分比表示分层32项树相比32叉树、32项树的延迟下降比例;↓表示分层32项树相比32叉树、32项树的延迟下降比例.
    下载: 导出CSV 
    | 显示表格

    需要注意的是,随着进程数的增大,32项树的延迟增加较缓慢,而分层32项树的延迟增加略快(分层32项树相比32项树的延迟下降比例由进程数为64时的32%下降为进程数为512时的24%). 这是因为,在裁剪胖树中,随着进程数的增大,32项树中每条链路上传输的最大聚合包数保持为16,故32项树的延迟变化不大;而分层32项树中每条链路上传输的最大聚合包数由1逐渐增大到31,故分层32项树的延迟会缓慢增加. 但可以肯定的是,随着进程数的进一步增大,分层32项树的延迟仍低于32项树,这是因为32项树中每2个相邻交换机间都需要传输16个聚合包,从而更易受网络噪声的干扰.

    除此之外,本文还在其他场景下测试了3种聚合树构建算法的消息延迟. 例如,利用更多超节点进行了测试,其网络拓扑采用3层裁剪胖树,故分层32项树可采用更多的层次. 此实验的测试结论与上述测试结论一致,即分层32项树延迟最低,32项树次之,32叉树延迟最高. 限于篇幅,不再赘述其详细测试数据.

    本节对Ⅰ型聚合树及Ⅱ型聚合树的性能进行对比. 测试环境如图17所示. 其中Ⅰ型聚合树采用64叉树进行构建,Ⅱ型聚合树的树根建在最高层的那个交换机上. 分别测试了不同进程数下2种类型聚合树的性能,Bcast-8 B及Bcast-2 KB的延迟如图18所示. 可以看出,Ⅱ型聚合树的延迟比Ⅰ型聚合树低1 μs左右.

    图  17  使用网络拓扑对比Ⅰ型聚合树及Ⅱ型聚合树性能
    Figure  17.  Network topology used to compare the performance of type Ⅰ and type Ⅱ aggregate trees
    图  18  Ⅰ型聚合树及Ⅱ型聚合树的性能对比
    Figure  18.  Performance comparison of type Ⅰ and type Ⅱ aggregate trees

    本节测试最小代价Ⅱ型聚合树构造算法的有效性以及不同通信模式下聚合树条目的使用情况.

    MPI集合通信中,一般将进程划分为2维或3维网格通信域,其每个维度中的每行或每列都是一个通信域. 本文测试了5种典型的通信模式,包括2种2维网格结构、2种3维网格结构,以及1种随机模式. 选择的2维网格结构中,256×160通信模式按拓扑结构划分通信域,模拟拓扑感知的通信模式,即第1维有160个通信域,故每个通信域都位于同一个超节点内;而202×202通信模式存在很多跨超节点的通信域,模拟拓扑无感的通信模式. 2种3维网格结构也是按类似原则进行划分的. 随机模式是指进程随机加入一个通信域.

    下面从2个方面证明最小代价Ⅱ型聚合树构造算法的有效性:一方面,最小代价Ⅱ型聚合树占用的聚合树条目数相比传统方法构建的Ⅱ型聚合树有显著下降;另一方面,最小代价Ⅱ型聚合树构建算法创建聚合树时的失败率相比传统的Ⅱ型聚合树也有显著下降.

    1) 聚合树占用的总条目数

    首先测试每种通信模式下聚合树占用的总条目数. 假设每个交换机内的聚合树条目数足够多. 对于每种通信模式,依次为每个通信域构建Ⅱ型聚合树,并统计占用的聚合树条目总数,结果如图19所示. 其中,传统方法构建的Ⅱ型聚合树是指利用集中式方法构建的物理树. 可以看出,所有通信模式下,最小代价Ⅱ型聚合树占用的条目总数明显低于传统方法构建的聚合树所占用的条目数,最少下降了90%. 这表明最小代价Ⅱ型聚合树算法在降低聚合条目使用量方面具有显著效果. 有些通信模式下,最小代价Ⅱ型聚合树的聚合树条目总数等于通信域个数,这是因为在这些通信模式下,每个通信域的最小代价Ⅱ型聚合树都仅使用1个交换机.

    图  19  不同通信模式下Ⅱ型聚合树使用的总聚合树条目数
    Figure  19.  Total count of aggregate tree entries used by type Ⅱ aggregate trees for different kinds of communication patterns

    2)创建聚合树时的失败率

    将每个交换机的聚合树条目数设为16,然后在每种通信模式下依次为每个通信域构建Ⅱ型聚合树,并记录创建失败的次数. 定义创建聚合树时的失败率为:=,结果如图20所示. 可以看出,最小代价Ⅱ型聚合树算法均能为每个通信域成功构建聚合树;而传统的Ⅱ型聚合树构建方法失败率很高,最高可达74.51%.

    图  20  不同通信模式下创建Ⅱ型聚合树的失败率
    Figure  20.  Failure rate of creating type Ⅱ aggregate trees in different communication patterns

    需要指出的是,将交换机的聚合树条目数设为更小的值后,某些通信模式下也存在不能创建最小代价Ⅱ型聚合树的情况,但其失败率仍低于传统的Ⅱ型聚合树构建方法,结果不再赘述.

    综上所述,最小代价Ⅱ型聚合树算法可以显著减少对交换机内聚合树条目资源的占用,从而可以支持创建更多的Ⅱ型聚合树.

    硬件集合通信中,聚合树对集合操作的性能具有重要影响. 构建聚合树时,需要综合考虑聚合树半径、宽度、负载均衡、网络噪声等的影响. 本文提出了硬件集合通信开销模型,并据此提出了3种构建聚合树的方法,包括:1)根据聚合包大小确定Ⅰ型聚合树的宽度;2)最小高度分层Ⅰ型聚合树构建方法;3)最小代价Ⅱ型聚合树构建方法. 然后在神威互连网络中对聚合树构建方法进行了全面测试,在存在网络噪声的情况下,分层Ⅰ型聚合树的消息延迟相比传统构建方法下降了24%~89%;最小代价Ⅱ型聚合树使用的交换机聚合条目数相比传统构建方法下降了约90%.

    下一步,我们将利用真实的应用程序对聚合树构建方法的性能进行更全面的测试. 另外,我们还将研究如何利用硬件集合通信提升长度较大的规约、广播等集合操作的性能,扩大硬件集合通信的适用范围.

    作者贡献声明:陈淑平提出研究思路,设计算法、实验,分析实验数据并撰写论文;尉红梅指导算法及完善实验方案;王飞、李祎负责算法实现、测试数据的整理与分析;何王全、漆锋滨提出研究课题,把握论文创新性,并对论文进行修改.

  • 图  1   用户重购偏好随重购数量变化的趋势

    Figure  1.   Trend of user’s repurchase preference varies with the number of repurchase

    图  2   基于多层信息融合的重购推荐方法

    Figure  2.   Repurchase recommendation method based on multi-level information fusion

    图  3   重购数量随时间变化图

    Figure  3.   The change of repurchase quantity over time

    图  4   本文方法与其它基准方法的对比

    Figure  4.   Comparison of our proposed method and other baseline methods

    图  5   参数性能变化图

    Figure  5.   Parameter performance variation diagram

    图  6   注意力权重热力图

    Figure  6.   Attention weight heat map

    表  1   数据统计

    Table  1   Data statistics

    产品顾客数产品数量购买天数周数平均购买天数
    面包243016526757410227.81
    牛奶246115598588410234.90
    下载: 导出CSV

    表  2   用户重购偏好趋势的回归分析

    Table  2   Regression Analysis of User Repurchase Preference Trend

    变量 面包回购牛奶回购
    Time0.575***(11.338)0.401***(9.526)
    Time2−1.021***(−9.641)−0.608***(−6.967)
    Time30.519***(7.602)0.291***(5.395)
    Price−0.388***(−23.413)−0.322***(−33.555)
    Discount0.228***(10.242)−0.851***(−51.602)
    UserFixedEffect控制控制
    样本量5839981558
    注:括号内为z统计量,***表示在1%的显著性水平下显著.
    下载: 导出CSV

    表  3   面包数据集的实验结果

    Table  3   Experimental Results on Bread Dataset

    模型RecallPrecisionNDCG
    Pop0.00840.00240.0032
    SHARE0.02950.00860.0266
    DREAM0.34750.10140.1299
    RecaNet0.38090.11100.1403
    CLEA0.21600.10240.0821
    本文0.45920.13390.1714
    下载: 导出CSV

    表  4   牛奶数据集的实验结果

    Table  4   Experimental Results on Milk Dataset

    模型RecallPrecisionNDCG
    Pop0.10700.03330.0252
    SHARE0.01740.00540.0036
    DREAM0.48480.14990.2054
    RecaNet0.51360.15970.2039
    CLEA0.46650.20590.1791
    本文0.57520.17890.2342
    下载: 导出CSV
  • [1]

    Liu Huafeng, Jing Liping, Qian Yuhua, et al. Adaptive local low-rank matrix approximation for recommendation[J]. ACM Transactions on Information Systems, 2019, 37(4): 1−34

    [2]

    Inman J J, Zeelenberg M. Regret in repeat purchase versus switching decisions: The attenuating role of decision justifiability[J]. Journal of Consumer Research, 2002, 29(1): 116−128 doi: 10.1086/339925

    [3]

    Bhagat R, Muralidharan S, Lobzhanidze A, et al. Buy it again: Modeling repeat purchase recommendations [C] //Proc of the 24th ACM SIGKDD Int Conf on Knowledge Discovery & Data Mining. New York: ACM, 2018: 62−70

    [4]

    Wang Chenyang, Zhang Min, Ma Weizhi, et al. Modeling item-specific temporal dynamics of repeat consumption for recommender systems [C] //Proc of the 28th Int Conf on World Wide Web. New York: ACM, 2019: 1977−1987

    [5]

    Kapoor K, Subbian K, Srivastava J, et al. Just in time recommendations: Modeling the dynamics of boredom in activity streams [C] //Proc of the 8th ACM Int conf on Web Search and Data Mining. New York: ACM, 2015: 233−242

    [6]

    See A, Liu P J, Manning C D. Get to the point: Summarization with pointer-generator networks [J]. arXiv preprint, arXiv: 1704.04368, 2017

    [7]

    Jacoby J, Speller D E, Kohn C A. Brand choice behavior as a function of information load[J]. Journal of Marketing Research, 1974, 11(1): 63−69 doi: 10.1177/002224377401100106

    [8]

    Degeratu A M, Rangaswamy A, Wu Jianan. Consumer choice behavior in online and traditional supermarkets: The effects of brand name, price, and other search attributes[J]. International Journal of Research in Marketing, 2000, 17(1): 55−78 doi: 10.1016/S0167-8116(00)00005-7

    [9]

    Hoch S J, Deighton J. Managing what consumers learn from experience[J]. Journal of Marketing, 1989, 53(2): 1−20 doi: 10.1177/002224298905300201

    [10]

    Hoyer W D. An examination of consumer decision making for a common repeat purchase product[J]. Journal of Consumer Research, 1984, 11(3): 822−829 doi: 10.1086/209017

    [11]

    Jacoby J, Jaccard J J, Currim I, et al. Tracing the impact of item-by-item information accessing on uncertainty reduction[J]. Journal of Consumer Research, 1994, 21(2): 291−303 doi: 10.1086/209398

    [12]

    Pierson P. Increasing returns, path dependence, and the study of politics[J]. American Political Science Review, 2000, 94(2): 251−267 doi: 10.2307/2586011

    [13]

    Luo Xueming, Andrews M, Song Yiping, et al. Group-buying deal popularity[J]. Journal of Marketing, 2014, 78(2): 20−33 doi: 10.1509/jm.12.0422

    [14]

    Atchariyachanvanich K, Sonehara N, Okada H. What are the benefits of continued purchasing through the Internet? A study of South Korean consumers [J]. Journal of Service Science and Management, 2008, 1(01): 101

    [15]

    Hellier P K, Geursen G M, Carr R A, et al. Customer repurchase intention: A general structural equation model[J]. European Journal of Marketing, 2003, 37(11/12): 1762−1800 doi: 10.1108/03090560310495456

    [16]

    Lee J, Lee J, Lee H, et al. An exploratory study of factors influencing repurchase behaviors toward game items: A field study[J]. Computers in Human Behavior, 2015, 53: 13−23 doi: 10.1016/j.chb.2015.06.017

    [17]

    Anderson A, Kumar R, Tomkins A, et al. The dynamics of repeat consumption [C] //Proc of the 23rd Int Conf on World Wide Web. New York: ACM, 2014: 419−430

    [18]

    Abdul-Muhmin A G. Repeat purchase intentions in online shopping: The role of satisfaction, attitude, and online retailers’ performance[J]. Journal of International Consumer Marketing, 2010, 23(1): 5−20 doi: 10.1080/08961530.2011.524571

    [19]

    Li Xiaolin, Zhuang Yuan, Lu Benjiang, et al. A multi-stage hidden Markov model of customer repurchase motivation in online shopping[J]. Decision Support Systems, 2019, 120: 72−80 doi: 10.1016/j.dss.2019.03.012

    [20]

    Pokryshevskaya E B, Antipov E A. The strategic analysis of online customers’ repeat purchase intentions[J]. Journal of Targeting, Measurement and Analysis for Marketing, 2012, 20: 203−211 doi: 10.1057/jt.2012.16

    [21]

    Graciola A P, De Toni D, De Lima V Z, et al. Does price sensitivity and price level influence store price image and repurchase intention in retail markets?[J]. Journal of Retailing and Consumer Services, 2018, 44: 201−213 doi: 10.1016/j.jretconser.2018.06.014

    [22]

    Ghezelbash S, Khodadadi H. Evaluating the impact of promotion price, product quality, service quality, customer satisfaction and repeating purchase incentives (Case study: Amiran chain stores) [J]. The Journal of Internet Banking and Commerce, 2017(22): 1−17

    [23]

    Suhaily L, Soelasih Y. What effects repurchase intention of online shopping[J]. International Business Research, 2017, 10(12): 113−122 doi: 10.5539/ibr.v10n12p113

    [24]

    He Ruining, McAuley J. Fusing similarity models with Markov chains for sparse sequential recommendation [C] //Proc of 16th IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2016: 191−200

    [25]

    He Ruining, Kang Wang Cheng, McAuley J. Translation-based recommendation [C] //Proc of the 11th ACM Conf on Recommender Systems. New York: ACM, 2017: 161−169

    [26]

    Yuan Fajie, Karatzoglou A, Arapakis I, et al. A simple convolutional generative network for next item recommendation [C] //Proc of the 12th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2019: 582−590

    [27]

    Yu Feng, Liu Qiang, Wu Shu, et al. A dynamic recurrent model for next basket recommendation [C] //Proc of the 39th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2016: 729−732

    [28] 钱忠胜,杨家秀,李端明,等. 结合用户长短期兴趣与事件影响力的事件推荐策略[J]. 计算机研究与发展,2022,59(12):2803−2815

    Qian Zhongsheng, Jiaxiu Jiaxiu, Li Duanming, et al. An event recommendation strategy combining users’ long-term and short-term interests and event influence[J]. Journal of Computer Research and Development, 2022, 59(12): 2803−2815 (in Chinese)

    [29]

    Wang Jianling, Ding Kaize, Zhu Ziwei, et al. Session-based recommendation with hypergraph attention networks [C] //Proc of the 21st SIAM Int Conf on Data Mining. Philadelphia, PA: SIAM, 2021: 82−90

    [30] 曾义夫,牟其林,周乐,等. 基于图表示学习的会话感知推荐模型[J]. 计算机研究与发展,2020,57(3):590−603

    Zeng Yifu, Mou Qilin, Zhou Le, et al. Session-aware recommendation model based on graph representation learning[J]. Journal of Computer Research and Development, 2020, 57(3): 590−603 (in Chinese)

    [31]

    Kurashima T, Althoff T, Leskovec J. Modeling interdependent and periodic real-world action sequences [C] //Proc of the 27th Int Conf on World Wide Web. New York: ACM, 2018: 803−812

    [32]

    Chen Jun, Wang Chaokun, Wang Jianmin, et al. Recommendation for repeat consumption from user implicit feedback[J]. IEEE transactions on Knowledge and Data Engineering, 2016, 28(11): 3083−3097 doi: 10.1109/TKDE.2016.2593720

    [33]

    Bai Ting, Zou Lixin, Zhao Xin, et al. CTrec: A long-short demands evolution model for continuous-time recommendation [C] //Proc of the 42nd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2019: 675−684

    [34]

    Ren Pengjie, Chen Zhumin, Li Jing, et al. Repeatnet: A repeat aware neural recommendation machine for session-based recommendation [C] //Proc of the 33rd AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2019: 4806−4813

    [35]

    Yu Yonghong, Wang Can, Wang Hao, et al. Attributes coupling based matrix factorization for item recommendation[J]. Applied Intelligence, 2017, 46: 521−533 doi: 10.1007/s10489-016-0841-8

    [36]

    Wang Shoujin, Wang Yan, Hu Liang, et al. Modeling user demand evolution for next-basket prediction [J]. IEEE transactions on Knowledge and Data Engineering, 2022(99): 1−14

    [37]

    Katz O, Barkan O, Koenigstein N, et al. Learning to ride a buy-cycle: A hyper-convolutional model for next basket repurchase recommendation [C] //Proc of the 16th ACM Conf on Recommender Systems. New York: ACM, 2022: 316−326

    [38]

    Hu Haoji, He Xiangnan, Gao Jinyang, et al. Modeling personalized item frequency information for next-basket recommendation [C] // Proc of the 43rd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2020: 1071−1080

    [39]

    Ariannezhad M, Jullien S, Li Ming, et al. ReCANet: A repeat consumption-aware neural network for next basket recommendation in grocery shopping [C] //Proc of the 45th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2022: 1240−1250

    [40]

    Qin Yuqi, Wang Pengfei, Li Chenliang. The world is binary: Contrastive learning for denoising next basket recommendation [C] // Proc of the 44th Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2021: 859−868

  • 期刊类型引用(1)

    1. LUO Haoran,HU Shuisong,WANG Wenyong,TANG Yuke,ZHOU Junwei. Research on Multi-Core Processor Analysis for WCET Estimation. ZTE Communications. 2024(01): 87-94 . 必应学术

    其他类型引用(4)

图(6)  /  表(4)
计量
  • 文章访问数:  214
  • HTML全文浏览量:  18
  • PDF下载量:  125
  • 被引次数: 5
出版历程
  • 收稿日期:  2023-03-30
  • 修回日期:  2023-06-11
  • 网络出版日期:  2023-06-25
  • 刊出日期:  2023-07-31

目录

/

返回文章
返回