时序相关任务的并行计算解决方案讨论
(Parallel computing solution for chronologically correlative tasks)
现实问题描述
想象一个设备网络,包括许多交换机、路由器、网关服务器、Radius服务器,等等。如果要集中式的监控各个设备的工作状态,就需要在网络中部署一个网络设备管理系统。从网管系统侧看来,所有设备都直接或间接与之相连,并通过各种可达的通信协议,诸如但不限于SNMP,定时或不定时的不间断的报告各自当前或历史和工作状态相关的数据。网管系统需要对所获得的设备信息进行计算,以维护和刷新系统内部用于表征实际设备的模型对象(该对象可能会包括至少一个有限状态机,和若干统计量),所有抽象对象构成一个映射实际网络的设备拓扑模型,这是系统实现设备管理和监控的基础。
就设备信息的计算而言,可能会有如下特征:
l 计算必须迅速,以保证分析结果的时效性;
l 同一时间切片上的数据量可能很大,主要取决于网络规模的大小;
l 基于前面两点,我们会考虑采用并行计算提高数据处理速度。而且不同设备产生的数据的处理不具有相关性,在保证时效性的前提下,对它们的处理顺序的改变不会影响计算结果。这是得以采用并行计算的前提;
l 但是同一设备的数据产生在时间上是有序的;网管系统对其处理顺序也需与其一致,否则可能会影响计算结果(后面将举例说明这点)。所以时序相关的数据计算必须保证被偏序执行-比如串行计算;
l 而且每个设备的数据随着时间的推移理论上是个无限集,它可以映射为正整数集(以系统运行后收到的该设备第一份数据为D(1),第二份为D(2),依此类推)。所以要在全集上进行重新排序然后再处理,是不可能的;
l 网管系统数据获取接口通常为一个或几个,和实际网络中的设备形成一对多的关系。也就是说每个接口获取的数据并不必然来自一个设备,必须在处理它们前分析其相关性,以决定何种计算方式。
在此举一个简化了的例子来说明考虑数据处理时序相关特征的重要性。想象只有正常、故障两种状态的一个设备。和该设备状态相关的只有一种告警信息,状态转换和事件的关系如图1所示。假设设备目前在正常状态下,先产生一个“告警产生”事件,紧接着又产生一个“告警消除”事件,设备应该最终仍旧处于正常状态。但由于某种原因,第二个事件先于第一个事件被处理,这种情况下,由于设备当前状态为正常,它会丢弃“告警消除”事件,然后“告警产生”事件会将设备转变为故障状态。
图1 网络设备状态机简化示例
一般性归纳
为了便于推演,使本文的讨论适用于同一类问题,这里试着对问题进行一般性归纳,以确保后面的讨论是在问题的一般性特征基础上,而不是基于具体的网管问题。
处理对象数据(target data)
是从数据源(设备)到处理机(网管系统,后面详细讨论),供处理机运算的信息。假设集合V={vi | i>0, i<=n}是数据源提供的所有n个描述自身的数据指标(或称变量)的全集。则每一个具体的数据消息D={v | v ∈ V}包含了V的一个子集的指标值,可能各有差异。但对于每一个D,必须包含可以用于计算相关性的指标,可以称为相关键(correlativity key);以及标识其时序特征的指标,可以称为数据的时间标签(timestamp)。
相关键(correlativity key)
任意两个数据D, D’,针对具体的处理算法,其相关性必须是确定的:
Correlativity (D, D’) ∈ {0, 1}
其中1表示全相关,0标识不相关。并非D中所有指标都需参与相关性计算,而是一个子集,可以称为相关键。在前面讨论的问题中,来自同一个设备的数据相关,否则就不相关。相关键就是标识数据源身份的指标,比如设备ID,设备IP,或者设备的Mac地址等。要注意具体问题中,相关键并不一定都由单指标组成,如果上述设备网络跨多个局域网,设备只有内网IP地址,考虑到属于不同局域网设备的IP地址可能重复,用设备IP地址和局域网网管地址组成相关键是可行的选择之一。
但不论相关键CK简单或复杂,为了解决问题的方便,我们可以寻找一种映射关系CF,将CK映射到一个相关因子(correlativity factor)集I上,使得
i = Cf (CK(D)), i ∈ I
I可以是正整数(或整数)子集,在网管问题中,给每一个设备编号,即形成设备ID,就是一种简单可行的Cf映射关系。
这样,数据相关性判断就可以归结为相关因子的比较:
Correlativity (D, D’) = (i = = i’ ? 1 : 0)
这里并非为了故弄玄虚。相关键的归纳是为了让讨论适用于可能更多的问题,而不仅仅局限于网络设备网管数据处理。相关因子的引入则是为了后面调度算法的简化-以相关因子作为输入的调度算法不用再考虑随具体情况变化的相关键,更具有通用性。
时间标签(timestamp)和时序索引(chronologic index)
在许多具体问题中,数据本身就带有其产生的时间,可以称为内置时间标签(inline timestamp),比如网管问题中的告警、心跳信息、话单数据等。但内置时间标签并不见得可用。考虑到其它具体问题中,时序相关的数据不见得一定要来自同一物理源,所以可能会出现有的数据有内置时间标签而有的没有的情况。或者即便有,由于不同源,它们的标准可能不一样(比如和不同的NTP服务器同步,甚至是系统时间),从而不具有可比性。
另一个选择就是数据到达处理器的时间,或称提交时间。虽然提交时间顺序并不总是和数据的本质时序严格一致,但实际应用证明,提交时序通常能比较好的反应数据的本质时序。在没有更好的选择的前提下,采用提交时序不失为一种次优的选择,而且可以简化问题的解决(将在后面讨论)。
在具体问题的解决过程中,我们并不一定(有时也会,将在后面讨论)关心数据的时间标签(TS),而更关心基于时间标签的数据顺序。在此引入时序索引j = CI ( TS(D) ),对于任意两个时序相关的D, D’,如果TS(D) < TS(D’),则可以j < j’,时序索引可以落在一个正整数(或非付整数)集合J上。数据的时序索引可以让我们知道先处理哪个,后处理哪个-当然,如果它们时序相关的话。
时序相关(chronologically correlative)
在此需要专门强调的是,时序相关并非数据的固有特征,即便它们包括了时间标签,时序相关取决于数据处理的业务逻辑或处理算法(前面我们表述为数据处理的时序相关的,或者数据针对具体处理算法的相关性)。比如,前面的网管问题中,同样是以设备告警为对象数据,告警次数的统计就是非时序相关的,而基于告警的设备状态计算就可能是时序相关的了。
任务(Task)和处理器(Processor)
加速数据处理的解决方案就是对数据处理的流程进行划分,分解成小任务,再映射到处理器上,实现并行计算甚至分布式计算。这里所说的处理器并非物理上的,而是虚拟处理器,如线程(Thread),不跨或跨物理边界的进程(intra/inter-box process)。对于离散的到达处理器的每一份数据D ij,可以定义对应的处理任务Task ij,其中i指任务的相关因子,j则是基于相关因子的任务时序索引值,如前所述。
鉴于并行计算中任务间的偏序关系可以用有向无环图DAG(directional acyclic graph)描述,刻画任务时序相关关系的DAG(T, E, A, D)是一个如图2所示的特殊距阵:
图2 时序相关任务距阵
其中T = {Task ij | i ∈ [1, m], j ∈ [1, ∞]}为任务集,E = { e ij = e[Task ij, Task ij+1] | i ∈ [1, m], j ∈ [1, ∞]} 为任务间时序关系集合。A = {a ij | i ∈ [1, m], j ∈ [1, ∞]}为任务计算量集合,D = {d ij | i ∈ [1, m], j ∈ [1, ∞]}是对应任务的通信量。
在执行过程中,任务间的通信方式依赖于虚拟机类型,比如可以采用队列、共享内存,套接字连接等,实现技术都很成熟,这里不展开讨论。时序相关任务解决方案要回答的问题主要有两个:
l 怎样组织虚拟处理器。处理器拓扑结构也可以用一个DAG表示。
l 将任务DAG映射到虚拟器DAG,即任务调度算法,将每一个任务分配给一个确定的处理器执行。
分享到:
相关推荐
计算机组成原理实验报告-时序生成电路实验 计算机组成原理实验报告-存储器,其中包含实验内同,实验目的,实验结果还有电路图
时序产生器是CPU中一个类似"作息时间"的东西,使计算机可以准确、迅速、有条不紊地工作。机器一旦被启动,即CPU开始取指令并执行指令时,操作控制器就利用定时脉冲的顺序和不同的脉冲间隔,有条理、有节奏地指挥机器...
网站流量预测任务第一名解决方案:从GRU模型到代码详解时序预测.docx
电网的在线暂态稳定性分析对于确定电网在受到干扰后是否将横越至稳态稳定工作点至关重要。 暂态稳定性分析包括近似实时地计算建模电网网络的代数方程和... 讨论了由于逐次计算的增加以及CPU和GPU之间相关的内存传输延迟
1.于ITU官网下载 2.可用于计算自定义分辨率时序
• 工业互联网背景 • 应用与数据的特性与挑战 • 容器技术与时序数据库 IoTDB • 联合解决方案介绍
论文研究-复杂自适应系统的MAS动态协作任务求解时序逻辑模型.pdf, 借鉴组织学思想将自适应系统中的自主运行单元抽象为Agent, 把复杂自适应系统视为多Agent组织, 从时间...
Educoder头歌单总线CPU设计(定长指令周期3级时序)(HUST)谭志虎 华中科技大学计算机组成原理实验计算机硬件系统设计 单总线CPU设计(定长指令周期3级时序)(HUST 第1关:MIPS指令译码器设计 第2关:定长指令周期---时序...
moto6800接口协议时序图,比较有用,查问题时可以对照对照
大规模时序异常检测商业解决方案:阿里云SLS智能巡检.docx
解决方案,研究报告,行业报告
头歌educoder教学实践平台计算机组成原理单总线CPU设计(定长指令周期3级时序)(HUST)。第1关—第6关,源代码txt格式。 第1关 MIPS指令译码器设计 第2关 定长指令周期---时序发生器FSM设计 第3关 定长指令周期---时序...
高速电路信号完整性分析与设计—时序计算.pdf,需要的可以下载
华科计算机组成原理实验 单总线CPU设计(定长指令周期3级时序)(HUST)解题报告对应资源: https://blog.csdn.net/Spidy_harker/article/details/106296219
详细介绍了计算机的开机时序 详细介绍了计算机的开机时序 详细介绍了计算机的开机时序详细介绍了计算机的开机时序
1. 时序时空数据库技术创新:TSDB技术的出现标志着时序时空数据库技术的创新和变革,解决了时序时空数据的存储、处理和分析问题。 2. 多维索引:TSDB技术架构采用了多维索引,能够高效地处理时序时空数据,满足了...
计算机组成原理实验运算器原理的DSN 也就是在Proteus仿真软件上进行的实验做出来的电路图
计算机组成原理 MIPS三级时序中断机制实现(HUST),已通关
:在满足时序、资源许可的前提下优化调度产品并行设计过程,缩短产品上市时间已成为当前研究的一个重点。 针对并行设计特点建立了设计任务调度的目标函数,提出了一种遗传算法。该算法用矩阵式染色体表示设计任务与...
Kaggle网页流量时序预测比赛第一名方案