logoChat01.ai

在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表如表5－4所示。分别写出延迟禁止表F、冲...

创建于：2025年5月28日

使用 O3 回答 Chat01

问题

在一个5段的流水线处理机上需经9拍才能完成一个任务，其预约表如表5－4所示。分别写出延迟禁止表F、冲突向量C；画出流水线状态转移图；求出最小平均延迟及流水线的最大吞吐率及其调度方案。按此流水调度方案输入6个任务，求实际吞吐率。

图中打钩的坐标是S1,t0;s1,t8;s2,t1;s2,t2;s3,t3;s3,t6;s3,t7;s4,t3;s4,t4;s5,t5;s5,t6
请你教我解决这道题

Python

python
# reservation table: 5 rows, 9 cols
rows=5
cols=9
table=np.zeros((rows,cols),dtype=int)
ticks=[(0,0),(0,8),(1,1),(1,2),(2,3),(2,6),(2,7),(3,3),(3,4),(4,5),(4,6)]
for r,c in ticks:
    table[r,c]=1
table

array([[1, 0, 0, 0, 0, 0, 0, 0, 1],
       [0, 1, 1, 0, 0, 0, 0, 0, 0],
       [0, 0, 0, 1, 0, 0, 1, 1, 0],
       [0, 0, 0, 1, 1, 0, 0, 0, 0],
       [0, 0, 0, 0, 0, 1, 1, 0, 0]])

Python

python
# Forbidden latencies up to 8
forbidden=set()
for l in range(1,cols):
    overlapped=(table[:,:cols-l] & table[:,l:]).any()
    if overlapped:
        forbidden.add(l)
forbidden

{1, 3, 4, 8}

Python

python
collision_vector=[1 if i in forbidden else 0 for i in range(1,cols)]
collision_vector

[1, 0, 1, 1, 0, 0, 0, 1]

Python

python
collision_vector_str=''.join(str(b) for b in collision_vector)
collision_vector_str

'10110001'

Python

python
# Rather than implement, compute MAL via algorithm of maximum cycle mean on SCG.
# Use algorithm: create directed edges labeled with latency values l which are allowed.
# states are bit patterns length L.
# forbidden latencies F fixed.

def allowed_latencies(state):
    # state bits: if bit (l-1) set, then latency l is forbidden at this moment.
    # So allowed latencies are those l between 1..L where (state>>(l-1))&1==0 and l not in forbidden?
    # Wait there is double condition: l not forbidden due to base collision but maybe state prohibit.
    # Actually base forbidden latencies already in F; but state includes conflicts due to previous tasks.
    allowed=[]
    for l in range(1,L+1):
        if l in forbidden_latencies: # base structural hazard
            continue
        if (state>>(l-1))&1:
            continue
        allowed.append(l)
    return allowed

def next_state(state,l):
    # shift right by l, dropping lowest l bits
    new_state=state>>l
    # now OR with base forbidden vector
    forbidden_bits=0
    for f in forbidden_latencies:
        forbidden_bits |= 1<<(f-1)
    new_state |= forbidden_bits
    # mask to L bits
    new_state &= (1<<L)-1
    return new_state

forbidden_bits=0
for f in forbidden_latencies:
    forbidden_bits |=1<<(f-1)
forbidden_bits

141

Python

python
# BFS build graph from state 0
graph=defaultdict(list)
queue=deque([0])
visited=set([0])
while queue:
    s=queue.popleft()
    for l in allowed_latencies(s):
        ns=next_state(s,l)
        graph[s].append((ns,l))
        if ns not in visited:
            visited.add(ns)
            queue.append(ns)
len(visited)

4

Python

python
visited

{0, 141, 143, 175}

Python

python
# small graph of 4 states
graph

defaultdict(list,
            {0: [(141, 2), (141, 5), (141, 6), (141, 7)],
             141: [(175, 2), (141, 5), (143, 6), (141, 7)],
             175: [(141, 5), (141, 7)],
             143: [(141, 5), (143, 6), (141, 7)]})

Python

python
# Now find minimal average latency cycle using Karp's algorithm
states=list(visited)
index={s:i for i,s in enumerate(states)}
n=len(states)
# adjacency lists with latency cost
edges=[]
for s in states:
    for ns,l in graph[s]:
        edges.append((index[s],index[ns],l))
edges

[(0, 2, 2),
 (0, 2, 5),
 (0, 2, 6),
 (0, 2, 7),
 (1, 2, 5),
 (1, 1, 6),
 (1, 2, 7),
 (2, 3, 2),
 (2, 2, 5),
 (2, 1, 6),
 (2, 2, 7),
 (3, 2, 5),
 (3, 2, 7)]

Python

python
# Actually simpler: for each cycle we compute average latency. Graph is small; we can search cycles.

cycles=[]

def dfs(path,node):
    if node in path:
        idx=path.index(node)
        cycle=path[idx:]
        cycles.append(cycle)
        return
    if len(path)>n:
        return
    for ns,l in graph[node]:
        dfs(path+[(node,l)], ns)

dfs([],0)
len(cycles)

0

Python

python
# Let's brute enumerate cycles by exploring up to say 10 steps.

def search_cycles(start,max_len=10):
    cycles=[]
    def backtrack(curr,path,costs):
        # curr state
        if len(path)>max_len:
            return
        for ns,l in graph[curr]:
            if ns==start:
                cycles.append((path+[l],costs+[l]))
            else:
                # avoid large path loops beyond 10
                backtrack(ns,path+[l],costs+[l])
    backtrack(start,[],[])
    return cycles

cycs=search_cycles(0,10)
cycs

[]

Python

python
# hmm maybe because path visited duplicate lat? Let's do again with cycles from any node.

def search_cycles_from(node,max_len=10):
    cycles=[]
    def backtrack(curr,path,latencies,visited):
        if len(latencies)>max_len:
            return
        for ns,l in graph[curr]:
            if ns==node:
                cycles.append(latencies+[l])
            elif len(latencies)<max_len:
                backtrack(ns,path+[curr],latencies+[l],visited+[ns])
    backtrack(node,[],[],[])
    return cycles

all_cycles=[]
for s in visited:
    all_cycles+=search_cycles_from(s,10)
all_cycles

, 5, 2, 5, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 2, 5, 5, 7, 6],
 [5, 2, 5, 5, 2, 5, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 2, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 2, 5, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 2, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 2, 5, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 2, 5, 2, 5, 6],
 [5, 2, 5, 5, 2, 7, 2, 5, 2, 7, 6],
 [5, 2, 5, 5, 2, 7, 2, 5, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 2, 5, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 2, 5, 6],
 [5, 2, 5, 5, 2, 7, 2, 5, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 2, 5, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 2, 7, 2, 5, 6],
 [5, 2, 5, 5, 2, 7, 2, 7, 2, 7, 6],
 [5, 2, 5, 5, 2, 7, 2, 7, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 2, 7, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 2, 7, 6],
 [5, 2, 5, 5, 2, 7, 2, 7, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 2, 7, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 2, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 2, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 2, 7, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 2, 5, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 2, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 2, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 2, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 2, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 2, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 5, 2, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 5, 2, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 2, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 2, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 5, 2, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 2, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 2, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 5, 2, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 5, 2, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 2, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 5, 2, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 2, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 2, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 5, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 2, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 7, 2, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 7, 2, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 2, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 7, 2, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 2, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 2, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 7, 2, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 7, 2, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 2, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 7, 2, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 2, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 2, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 5, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 5, 7, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 2, 5, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 2, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 2, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 2, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 2, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 2, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 5, 2, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 5, 2, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 2, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 2, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 5, 2, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 2, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 2, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 5, 2, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 5, 2, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 2, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 5, 2, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 2, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 2, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 5, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 2, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 7, 2, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 7, 2, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 2, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 7, 2, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 2, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 2, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 7, 2, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 7, 2, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 2, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 7, 2, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 2, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 2, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 2, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 2, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 2, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 2, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 2, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 2, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 2, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 5, 2, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 5, 2, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 5, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 5, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 5, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 5, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 7, 2, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 7, 2, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 7, 5, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 7, 5, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 7, 7, 5, 6],
 [5, 2, 5, 5, 7, 7, 7, 7, 7, 6],
 [5, 2, 5, 5, 7, 7, 7, 7, 7, 7, 6],
 [5, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 2, 5, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 2, 5, 2, 7, 6],
 [5, 2, 5, 7, 2, 5, 2, 5, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 2, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 2, 5, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 2, 5, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 2, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 2, 5, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 2, 7, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 2, 7, 2, 7, 6],
 [5, 2, 5, 7, 2, 5, 2, 7, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 2, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 2, 7, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 2, 7, 6],
 [5, 2, 5, 7, 2, 5, 2, 7, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 2, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 2, 7, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 2, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 2, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 2, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 2, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 2, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 5, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 5, 2, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 5, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 5, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 5, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 5, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 7, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 7, 2, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 7, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 7, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 7, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 5, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 5, 7, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 2, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 2, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 2, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 2, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 2, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 5, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 5, 2, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 5, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 5, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 5, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 5, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 7, 2, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 7, 2, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 7, 5, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 7, 5, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 7, 7, 5, 6],
 [5, 2, 5, 7, 2, 5, 7, 7, 7, 6],
 [5, 2, 5, 7, 2, 5, 7, 7, 7, 7, 6],
 [5, 2, 5, 7, 2, 7, 2, 5, 2, 5, 6],
 [5, 2, 5, 7, 2, 7, 2, 5, 2, 7, 6],
 [5, 2, 5, 7, 2, 7, 2, 5, 5, 5, 6],
 [5, 2, 5, 7, 2, 7, 2, 5, 5, 6],
 [5, 2, 5, 7, 2, 7, 2, 5, 5, 7, 6],
 [5, 2, 5, 7, 2, 7, 2, 5, 6],
 [5, 2, 5, 7, 2, 7, 2, 5, 7, 5, 6],
 [5, 2, 5, 7, 2, 7, 2, 5, 7, 6],
 [5, 2, 5, 7, 2, 7, 2, 5, 7, 7, 6],
 [5, 2, 5, 7, 2, 7, 2, 7, 2, 5, 6],
 [5, 2, 5, 7, 2, 7, 2, 7, 2, 7, 6],
 [5, 2, 5, 7, 2, 7, 2, 7, 5, 5, 6],
 [5, 2, 5, 7, 2, 7, 2, 7, 5, 6],
 [5, 2, 5, 7, 2, 7, 2, 7, 5, 7, 6],
 [5, 2, 5, 7, 2, 7, 2, 7, 6],
 [5, 2, 5, 7, 2, 7, 2, 7, 7, 5, 6],
 [5, 2, 5, 7, 2, 7, 2, 7, 7, 6],
 [5, 2, 5, 7, 2, 7, 2, 7, 7, 7, 6],
 [5, 2, 5, 7, 2, 7, 5, 2, 5, 5, 6],
 [5, 2, 5, 7, 2, 7, 5, 2, 5, 6],
 [5, 2, 5, 7, 2, 7, 5, 2, 5, 7, 6],
 [5, 2, 5, 7, 2, 7, 5, 2, 7, 5, 6],
 [5, 2, 5, 7, 2, 7, 5, 2, 7, 6],
 [5, 2, 5, 7, 2, 7, 5, 2, 7, 7, 6],
 [5, 2, 5, 7, 2, 7, 5, 5, 2, 5, 6],
 [5, 2, 5, 7, 2, 7, 5, 5, 2, 7, 6],
 [5, 2, 5, 7, 2, 7, 5, 5, 5, 5, 6],
 [5, 2, 5, 7, 2, 7, 5, 5, 5, 6],
 [5, 2, 5, 7, 2, 7, 5, 5, 5, 7, 6],
 [5, 2, 5, 7, 2, 7, 5, 5, 6],
 [5, 2, 5, 7, 2, 7, 5, 5, 7, 5, 6],
 [5, 2, 5, 7, 2, 7, 5, 5, 7, 6],
 [5, 2, 5, 7, 2, 7, 5, 5, 7, 7, 6],
 [5, 2, 5, 7, 2, 7, 5, 6],
 [5, 2, 5, 7, 2, 7, 5, 7, 2, 5, 6],
 ...]

Python

python
# list is huge
len(all_cycles)

60489

Python

python
# compute average latency for each cycle
min_avg=INF
best_cycle=None
for latencies in all_cycles:
    avg=sum(latencies)/len(latencies)
    if avg<min_avg:
        min_avg=avg
        best_cycle=latencies
min_avg

3.5

Python

python
best_cycle[:20]

[2, 5]

Python

python
starts=[0]
lat_seq=[2,5]*5  # will produce more
for l in lat_seq[:5]: # need 5 latencies to produce 6 tasks
    starts.append(starts[-1]+l)
starts

[0, 2, 7, 9, 14, 16]

Python

python
last_completion=starts[-1]+9
total_time=last_completion-starts[0]
tp=6/total_time
tp

0.24

Python

python
total_time

25

Python

python
[bin(s)[2:].zfill(8) for s in visited]

['00000000', '10001111', '10001101', '10101111']

Python

python
state_labels={s:bin(s)[2:].zfill(8) for s in visited}
graph_labels={state_labels[s]:[(state_labels[ns],l) for ns,l in graph[s]] for s in graph}
graph_labels

{'00000000': [('10001101', 2),
  ('10001101', 5),
  ('10001101', 6),
  ('10001101', 7)],
 '10001101': [('10101111', 2),
  ('10001101', 5),
  ('10001111', 6),
  ('10001101', 7)],
 '10101111': [('10001101', 5), ('10001101', 7)],
 '10001111': [('10001101', 5), ('10001111', 6), ('10001101', 7)]}

思考

Building the state transition diagram

For the task at hand, I need to build a state transition diagram by

Thought for 3m 21s

回答

1 预约表复现

（5 条流水线段 S1–S5，9 个拍 t0–t8；“●”表示本拍该段被占用）

段\拍012345678
S1●●
S2●●
S3●●●
S4●●
S5●●

2 延迟禁止表 F

把原表再向右平移 l 拍并与原表相“与”，若出现“●”重叠，则 l 为禁止延迟。9 拍流水线只需检查 1 ~ 8：

延迟 l12345678
冲突？✓✓✓✓

F = { 1, 3, 4, 8 }

3 冲突向量 C

用 1 表示禁止延迟，按 l = 1 … 8 排列：

C = 1 0 1 1 0 0 0 1   &rarr;   10110001_2

4 流水线状态转移图

1 状态（4 个）：8 位移位寄存器的内容

text
S0 = 00000000   (初态)  
S1 = 10001101  
S2 = 10001111  
S3 = 10101111

位 i=1…8 为 “1” 代表接下来 i 拍因以往启动而不允许再启动。

2 可选延迟：在某状态下可启动的最小 l，是
  • l 不在 F 且
  • 当前状态寄存器第 (l-1) 位为 0。

3 转移：启动后把寄存器右移 l 位，再把 C “或” 入寄存器。

下表即转移图（边上标的是选择的延迟 l）：

由\到S0S1S2S3
S02,5,6,7
S15,762
S25,76
S35,76

5 最小平均延迟 (MAL) 与最大吞吐率

在状态图中找 平均延迟最小的有向环。

  • Greedy/最小平均环算法 ⇒ 环 <2,5>，平均延迟
L‾min⁡=2+52=3.5  拍/任务\overline{L}_{\min} = \frac{2+5}{2}=3.5\;\text{拍/任务}

最大吞吐率

Tmax⁡=1L‾min⁡=13.5≈0.286 任务/拍T_{\max}= \frac{1}{\overline{L}_{\min}} = \frac{1}{3.5}\approx 0.286\ \text{任务/拍}

6 最优调度方案

按周期序列 〈2, 5〉 重复启动：

text
任务 1: t = 0
任务 2: t = 2
任务 3: t = 7
任务 4: t = 9
任务 5: t = 14
任务 6: t = 16
...   之后每 2,5,2,5 周期交替

7 输入 6 个任务时的实际吞吐率

  • 每个任务内部仍需 9 拍完成。
  • 第 6 个任务启动于 t=16，完成于 t=25。
  • 总历时：25 − 0 = 25 拍。
T实际=6 个任务25 拍=0.24 任务/拍T_{\text{实际}} = \frac{6\ \text{个任务}}{25\ \text{拍}} = 0.24\ \text{任务/拍}

实际值低于理论上限 0.2860.286 的原因是 起步阶段的流水线充填时间 无法避免；任务数越多，实际吞吐率越趋近 Tmax⁡T_{\max}。

解题流程小结

  1. 画预约表 → 2. 求禁止延迟 F → 3. 得冲突向量 C
  2. 构造状态图（8 位寄存器 + 原始冲突向量并入）
  3. 找最小平均环 → 得 MAL 与 Tₘₐₓ
  4. 输出循环调度序列，再计算所给任务数下的实际吞吐率。

照此步骤，你可以处理任何类似的流水线调度题目。祝学习顺利!

分享这个问答