Home TileLink笔记(二):序列化、死锁避免、操作与消息
Post
Cancel

TileLink笔记(二):序列化、死锁避免、操作与消息

在上一节中我们简单了解了TileLink总线协议,包括总体架构与信号描述。具体来说,TileLink有三种协议扩展,即TL-UL、TL-UH和TL-C,有五个通道,分别为A、B、C、D和E,其中B、C和E为TL-C独有。在这一节中我们继续讨论序列化、死锁避免、操作与消息。

序列化

TileLink中的五个通道实现为五个物理隔离的单向并行总线。许多TileLink消息包含有效的数据负载,而根据消息和数据总线的大小,可能需要跨多个时钟周期发送,多拍的信息则通常被称为突发传输或簇发(burst),不过没有数据载荷的TileLink消息总是在单拍中完成。

流量控制规则

为了实现正确的ready和valid信号握手,需要遵守以下规则:

  • 当ready信号为低时,接收者不能处理数据并且发送者认为该拍内的数据未被处理。

  • 当valid信号为低时,接收者应当认为该数据信号并不是一个正确的TileLink数据。

  • valid必须与ready信号独立,如果一个发送者希望发送一拍数据,则必须使能一 个valid信号,同时该valid信号是与接收者的ready信号独立的。

  • 从ready到valid信号或者任何数据或控制信号之间不能存在任何组合逻辑路径。

对于能够携带簇发的TileLink的通道,有着额外的规则约束。一个簇发一旦第一拍数据 被接收,直到最后一拍数据传输结束都认为处于传输过程中。当一个数据包处于传输过程中 时,如果valid信号为高,发送者必须满足:

  • 只有同消息的簇发的一拍数据。

  • 控制信号与第一拍相同。

  • 数据为与之前拍数据的地址再加上按数据总线的字节宽度得到的地址所对应的数据。

2-1 在一个64-bit的A通道中,6个消息的Ready-Valid信号实例

在上面的例子中,F消息的信号长度为2^5=32字节,需要4拍来传输;J消息操作码为4,表示一个Get消息,不携带任何数据,单拍即可完成。

2-2 在一个64-bit的D通道中,6个消息的Ready-Valid信号实例

请求-响应消息排序

我们现在定义在一个具有多拍数据包的情况下,发送响应消息时的规则。在如下情况下,响应消息的第一拍可以出现在响应通道上:

  • 在请求消息被接收了的同一个周期出现,但不会在这周期之前出现。

  • 在请求消息的第一拍握手成功之后的任意时间

跟随在包的响应消息的第一拍后的多拍信号可以在任意延迟后出现,但与此同时,不能有来自其他消息的任一拍数据交错地插入此次传输中。

簇发响应

2-3 Get (4) 和 AccessAckData (1) 在一个8字节宽度总线上的最小与最大延迟

上图描述了两个Get操作。Get操作的请求消息(操作码4)从通道A发出,两个消息都访问32字节,在8字节的总线上分4拍取回数据,4拍的AccessAckData(操作码1)回复消息到达通道D。第一个回复消息在一个任意的延迟之后到达,主端接口必须要能够无限期地等待回复消息,在TileLink互联网络中不存在超时设定;第二个Get操作在请求消息被接收的同一个周期内即被回复,这种重叠情况在Get第一拍的信号被接收之后是允许的,但回复消息不能再提前出现,因为第二个Get首次出现时,a_ready为低,请求消息被拒绝了,d_valid信号也必须为低。

簇发请求

2-4 PutFullData (0) 和 AccessAck (0) 在一个8字节宽度总线上的最小与最大延迟

上图描述了两个Put操作。PutFullData请求消息(操作码0)在通道A发出,对应的AccessAck回复消息(操作码0)则在通道D返回。

簇发请求与响应

2-5 ArithmeticData (2) 和 AccessAckData (1) 在一个8字节宽度总线上的延迟

同时含有数据载荷的请求和响应消息适用和之前相同的规则。上图描述了由一个分别都带有数据载荷的请求和响应消息所组成的原子性操作,对于大小为4,16字节(2拍)的操作,要么在请求和响应消息之间存在较长的延迟,要么两者的各拍信号重叠。

字节通路

带有数据域的TileLink通道总是自然地以小端对齐方式运载数据载荷,一个字节通路传输的数据的地址的最低一部分总是相同的,如下图所示。

2-6 在一个16字节宽度总线上的数据载荷分布

在带有掩码(mask)域的通道A和B上,所有的无效字节通路的掩码位必须为低。除了PutPartialData以外的消息,所有的有效字节通路的掩码的信号必须为高。掩码信号也被其他不带数据载荷的消息使用,当操作需要使用的大小小于数据总线时,掩码应该要按带有数据载荷的信号时一样生成。对于比数据总线大小更大的操作,掩码的所有位数都应该拉高,尽管消息仍为一拍,如下图所示。

2-7 字节通路掩码的实例

死锁避免

TileLink被设计为可以完全避免死锁,为了保证一个TileLink拓扑网络不会产生死锁,我们提出一些一致性系统必须遵守的规则,如下所示:

2-8 TileLink网络需要遵守的规则

术语定义

  1. 接受(accept)一拍:若发送者在某个通道上把valid信号拉高,接收者若把ready信号拉高则接受一拍。

  2. 拒绝(reject)一拍:若发送者在某个通道上把valid信号拉高,接收者若把ready信号拉低则接受一拍。

  3. 撤回(retract)一拍:若接收者拒绝一拍,发送者可以拉低valid或在下一拍修改控制或数据信号来撤回一拍。

  4. 呈现(present)一拍:若valid拉高且所有控制和数据信号在ready也拉高之前都保持不变,称之为呈现一拍。

  5. 进行中(in progress):一个消息正在进行,表示从被接受的第一拍到最后一拍被接受之间的这段时间。

  6. 传输中(in flight):一个消息正在进行,表示从被呈现的第一拍到最后一拍被接受之间的这段时间。

  7. 请求消息:需要一个对应的响应消息,所有的TileLink操作都从某个通道的请求消息开始。

  8. 响应消息:跟随在请求消息之后的响应。

  9. 已收到的(received)消息:从簇发传输的第一拍被接受开始,消息被收到。

  10. 已回答的(answered)消息:收到的请求被响应后,消息被回答。

  11. 代理(agent):TileLink系统中的参与者,有一或多个TileLink链路。

  12. 优先级:一个消息的优先级与对应通道的优先级对应,响应消息的优先级总是比对应请求的优先级高,转发消息的优先级也更高。

  13. 最终事件:一个事件在任意长但并非无穷长之后最终发生。

  14. 向前推进:当所有呈现的拍最终被接受,且所有收到的请求最终被回答时,系统可以向前推进。

  15. 不活动的(quiescent):当没有添加新的消息时,系统处于不活动的状态,注意尽管TileLink保证不出现死锁,但仍然可能产生活锁或饥饿状态。为了限制这种情况,代理只被允许发送n+rf个消息,包括n为该代理允许发送的新消息、r为该代理接收的消息以及f为该代理为每个收到的消息允许发送的后续消息。

符合或不符合协议要求的代理示例

周期性转发的主设备(不符合)

一个代理有一个主接口和一个从接口,在A通道接受请求消息,但在转发消息时只在偶数周期拉高valid信号。这个代理不符合协议要求,原因是该代理不能完整呈现转发的消息,不能保证最终回答一个收到的请求。

等待刷新(符合)

一个DDR控制器周期性地无法处理请求,在这段时间内无条件地拉低所有ready信号,但注意到该代理仍然最终可以接受呈现的拍,因此还是符合协议要求的。

等待消息被接收(不符合)

一个代理有两个用于发送消息的链路,在链路1上发起簇发传输A,并且几拍中的第一拍被接受,表明消息已被接收,但仍在传输中,然后在链路2上发起簇发传输B,此时A的传输还未结束。在恢复A之前等待B被接受是不符合协议要求的。

非常慢的仲裁器(符合)

考虑一个具有三个链路的TL-UH代理,仲裁来自两条链路的A通道请求,并转发到第三条链路的A通道,但该仲裁器的吞吐量非常低。

代理空闲时将从任一输入的A通道中选择一个valid请求,一旦选择了一个请求,就会在另一个A通道上拉低ready信号,并在所选链路和输出链路之间连接ready和valid(通道A和D)。一旦请求的所有拍都已被输出通道接受,代理在两个输入A通道上拉低ready信号,并等待响应消息的最后一拍被所选的通道接受。

该代理符合规则2,因为可以假设输入的A通道都遵守规则2,因此其输出的A通道请求将呈现接收到的请求的所有节拍,D通道也同理。

假设代理正在处理输入的一个消息,在转发链路上分别有一个未回答或进行中的消息。由于该链路的优先级高于输入的链路,因此适用规则3,并且代理可以无限期地拒绝后续提交的A通道请求。

假设代理空闲并且没有输入呈现消息,这种情况满足规则3i,因为没有消息可以接受,同时也满足规则3ii,因为只有在收到的请求被回答时,仲裁器才会再次空闲。

代理图

每个TileLink网络都由TileLink链路和这些链路连接的代理组成,该网络可以表示为代理图,其中每个代理都是一个顶点,每个链路都是从主节点指向从节点的有向边,如下图所示。

2-9 一个小型RISC-V系统的代理图示例

操作与消息

带有主端接口的TileLink代理通过执行各类操作与共享存储系统进行交互,操作可以完成我们希望的的对地址范围的修改,可能是数据值,可能是这段地址内数据的权限,也可能是在存储层次中的位置,操作通过在通道内传输的具体消息的交换来实现。为了支持一个操作的实现,我们需要支持组成该操作的所有消息。我们详细描述每个操作的具体的消息交换过程,操作分为三个兼容级别,即TL-UL、TL-UH和TL-C。

操作分类

TileLink 操作能被分为下列三组:

  • Accesses (A) 在具体的地址读或写数据。

  • Hints (H) 只是提供一些信息,没有实际的影响。

  • Transfers (T) 在拓扑网络中改变权限或移动缓存拷贝。

不是每个TileLink代理都需要支持所有操作。取决于其的TileLink兼容级别,一个代理需要支持的操作如下表所列。

2-10 TileLink操作总览

消息分类

2-11 所有操作(蓝色)和对应的消息(紫色),虚线箭头表示请求和响应的配对

操作通过在五个TileLink通道内交换消息来执行。某些消息携带数据载荷,而有些则没有。如果一个TileLink消息携带数据载荷,那么其消息名以Data结尾。不是每一个通道都支持所有类型的消息。某些数据的到达必然会导致最终会有一个回复消息发送到请求发出者。带有回复的操作和消息分类如上图所示。下面两张表分别为通过兼容级别和操作对TileLink用到的消息进行分组,以及以通道和操作码来对消息进行排序。

2-12 通过操作和兼容级别进行分组的TileLink消息总览

2-13 通过通道与操作码进行排序的TileLink消息

注意到存在不同消息类型有着相同的操作码,不同的通道对于操作码有着不同的命名空间。在任何指定的通道内,每一个可能的消息类型有着独有的操作码。不管是在哪些通道内被进行交换的,相同类型的消息有着相同的操作码。操作码空间通过消息内容的有效解码进行分配。

寻址

TileLink通道内的所有地址都是物理地址。从TileLink有向无环图中的节点出发,每一个有效地址必须导向一条唯一通往一个具体的从端的路径。在TileLink中,地址决定了哪些操作是可以执行的,哪些效果可以产生,哪些排序约束可以施加。能被添加为一个地址空间的属性包括:兼容级别、存储一致性模型、可缓存性、FIFO排序要求、可执行性、特权等级、以及任何服务质量保证。

2-14 两个主代理M0和M1都可以访问从代理S0,但是只有M1可以通过缓存C访问从代理S1

源与目的地标识符

2-15 TileLink传输路径域总览

TileLink中并不是所有的消息都是根据地址来路由。尤其是,回复消息必须返回到正确的请求者。为支持此功能,TileLink通道包括了一个或更多的与本地链路相关的事务标识符域。这些域与address域一起用于路由消息,并且保证每一个发送中的消息能被特定操作唯一标识,如上表所示。

操作排序

在一个TileLink拓扑网络中,在任意给定时间内会有多个操作在进程中。这些操作可能以任意的顺序完成。为了确保主端能在一个操作完成后,再执行其他操作,TileLink要求从端在操作结束时及时发送一个回复消息。因此,如果处理器要确保两个写操作X和Y的顺序被其他所有代理获取时都是一致的,那么处理器发送X的PutFullData后,必须等待AccessAck回复,在此之后,才发送Y的PutFullData

TileLink的从端,包括缓存,不能在Put操作确认前就将数据写回。唯一的约束是,一旦确认消息发出后,整个拓扑网络不能观察到过去的状态,这是因为在确认消息发出后,所有的被缓存的数据的拷贝都必须是已更新的。例如,对于一个Put操作,其他缓存要么被Probe现有的数据拷贝,要么通过PutFullData将消息前递给其他缓存,并且在确认原始的请求消息前,收集对应的回复消息。

发射回复消息的代理需要保证它们接收的操作是一个有效的序列。例如,假设一个代理接收了两个Put,X和Y,并且都没有被确认,必须选择一定的顺序,例如说是X在Y之前。如果选择了这样的顺序,必须保证只有三个状态,X与Y前的状态,X之后且Y之前的状态和X与Y之后的状态。代理不一定要以这样的顺序发射回复消息。然而,在代理已发射了一条回复之后,例如Y,如果此时接受了新的操作Z,那么Z必须排在Y之后。

这些规则确保每个代理看到的全局操作排序与主端的确认信号引导的局部排序是一致的。处理器可以等待发出的确认消息返回后再发起其他请求,来实现fence指令。这样的能力使得多处理器在TileLink的共享存储系统中,安全地同步执行操作。

This post is licensed under CC BY 4.0 by the author.

TileLink笔记(一):架构与信号描述

TileLink笔记(三):TL-UL