多线程并行执行装置、广播流再现装置、广播流储存装置、储存流再现装置、储存流再编码装置、集成电路、多线程并行执行方法、多线程编译器

摘要

在暂定数据保存部(104)中保存有值“3”和迭代号码“3”的情况下，在数据更新管理部(103)接收到与迭代号码“2”建立了联系的值“2”的情况下，数据更新管理部(103)通过将两迭代号码的大小关系比较，判断为不将接收到的信息覆盖到暂定数据保存部(104)中。然后，数据更新管理部(103)如果从多线程执行部(102)接收到表示并行执行的结束的结束信息，则将保存在暂定数据保存部(104)中的值“3”反映到确定数据保存部(105)中。

说明书

技术领域

本发明涉及将循环处理中的重复单位分为多个线程而并行执行的技 术。

背景技术

在将某一个循环处理用多个线程分担而并行地处理(多线程化)时， 需要在并行处理的情况和逐次处理的情况的两情况下最终的变量的值为相 同的值。将其称作“终值保证”。

作为实现这样的终值保证的技术，已知有专利文献1、2的技术。

在专利文献2中，在使某个循环处理并行化时，按照并行过程设置区 域。然后，在对在各并行过程中定义的变量附加表示是否是最终的重复的 代码后，保存到对应的区域中。

并且，如果对于循环处理的全部的并行过程的执行完成，则以对保存 在各区域中的变量附加的代码为线索，确定与担当最终的重复的过程对应 的变量。接着，通过将所确定的变量取出，能够正确地参照变量的值。

先行技术文献

专利文献

专利文献1：日本专利第3269639号公报

专利文献2：日本特开平5-181687号公报

发明概要

发明要解决的课题

但是，如果将专利文献2的方法应用到上述的循环处理的多线程化中， 则按照线程设置区域，将由各线程处理的变量保存到该区域中。

因此，有与线程数成比例、需要的存储器区域增大的问题。例如，如 果线程数是16个，则对应需要16个存储器区域。

发明内容

本发明是解决这样的问题的，目的是提供一种能够以少量的存储器区 域实现终值保证的多线程并行执行装置。

解决课题的手段

有关本发明的多线程并行执行装置，其特征在于，具备：执行机构， 将一个循环处理中的重复单位分为多个线程并行执行；接收机构，在上述 执行机构并行执行的期间中，从上述执行机构接收表示各线程中的重复单 位的执行的结果的值、和表示该重复单位的顺序的顺序信息的组；保存机 构，用来保存上述值和上述顺序信息的组；控制机构，在上述接收机构接 收到上述组的情况下，基于由接收到的上述顺序信息与保存在上述保存部 中的顺序信息分别表示的顺序的先后，控制是使接收到的上述顺序信息和 对应的上述值的组覆盖还是不覆盖到上述保存部中；确定机构，如果由上 述执行机构进行的并行执行结束，则确定保存在上述保存机构中的值作为 上述一个循环处理的执行结果。

发明效果

根据有关本发明的多线程并行执行装置，如果接收机构接收到值和顺 序信息的组，则能够使是否向保存机构覆盖接收到的信息基于由接收到的 顺序信息和保存的顺序信息分别表示的顺序的先后而不同，所以能够适当 地进行覆盖控制而实现终值保证。

此外，通过向保存机构覆盖值和顺序信息，使得即使多线程数增加、 也不会增加上述保存机构的存储器区域。

附图说明

图1是多线程并行执行装置101的功能块图。

图2是表示数据更新管理部103中的处理的流程图。

图3是覆盖要否的判断表。

图4是表示实例程序1、和将该实例程序1逐次执行的情况下的处理结 果的图。

图5是表示将图4的实例程序1利用线程1、2并行执行的情况下的各 迭代的处理结果的图。

图6是说明以迭代号码1→3→2→4的顺序执行的情况下的、信息的流 动和暂定数据保存部104的覆盖的有无的图的前半。

图7是说明以迭代号码1→3→2→4的顺序执行的情况下的、信息的流 动和暂定数据保存部104的覆盖的有无的图的后半。

图8(a)是表示设定了断点的实例程序2的图，图8(b)是表示在将 实例程序2逐次执行的情况下、在第2个迭代中中断的状况的形象图，图8 (c)是将实例程序2利用线程1、2并行执行时的形象图。

图9是多线程并行执行装置901的功能块图。

图10是表示数据更新管理部903中的处理的流程图。

图11是覆盖要否的判断表。

图12是多线程并行执行装置1201的功能块图。

图13是多线程编译器1302的结构图。

图14是表示处理线程程序生成部1304中的处理的流程图。

图15是集成电路1501的功能块图。

图16是广播流再现装置1601的功能块图。

图17是广播流储存装置1701的功能块图。

图18是储存流再现装置1801的功能块图。

图19是储存流再编码装置1901的功能块图。

图20是表示变形例的图。

图21是表示数据更新管理部103中的处理的流程图。

图22是多线程并行执行装置2201的功能块图。

具体实施方式

以下，参照附图对本发明的实施方式进行说明。

(实施方式1)

如图1所示，多线程并行执行装置101具备多线程执行部102、数据更 新管理部103、暂定数据保存部104、确定数据保存部105。

多线程执行部102例如由CPU构成，执行程序。

该程序包括相当于循环处理的重复单位(称作迭代)的命令群。

多线程执行部102将该迭代分为多个线程而并行执行。

在该并行执行中，多线程执行部102每当各线程中的迭代结束，就将 表示迭代的执行结果的值、和表示已执行的迭代在循环处理中是第几个(该 顺序与假设将循环处理逐次执行时的执行的顺序一致)的迭代号码i(th) 的组向接收部111发送。

此外，在并行执行结束时，多线程执行部102对结束判断部113目的 地发送表示结束的结束信息。

数据更新管理部103根据由多线程执行部102进行的并行执行，管理 暂定数据保存部104及确定数据保存部105的数据更新。

数据更新管理部103具备接收部111、保存控制部112、结束判断部113、 确定部114。

接收部111接收从多线程执行部102发送来的、包括表示迭代的执行 结果的值与表示已执行的迭代在循环处理中是第几个的迭代号码i(th)的 组的信息。

保存控制部112在没有暂定数据保存部104的数据的情况下，将接收 部111接收到的值与迭代号码i(th)的组保存到暂定数据保存部104中。 此外，保存控制部112在暂定数据保存部104中已经保存有对应的信息的 情况下，按照后述的条件，进行是否覆盖保存的控制。

结束判断部113如果从多线程执行部102接收到上述结束信息，则判 断并行执行的结束。并且，如果判断为结束，则对确定部114通知该消息。

另外，并行执行结束的判断并不限定于此，也可以使用一般的方法。

确定部114如果从结束判断部113接受到结束判断的通知，则将保存 在暂定数据保存部104中的值取出，向确定数据保存部105反映(复制)。

暂定数据保存部104是用来在由多线程执行部102进行的并行执行中 保存上述值和迭代号码i的。

另外，在本说明书中，将保存在暂定数据保存部104中的迭代号码表 述为“i”，将接收部111从多线程执行部102接收到的迭代号码区别表述为 “i(th)”。

确定数据保存部105是用来保存作为上述一个循环处理的执行结果的 值的。

另外，两保存部104、105例如由RAM(Random Access Memory)构 成。

接着，参照图2对多线程并行执行时的数据更新管理部103的动作进 行说明。

首先，保存控制部112进行暂定数据保存部104的内容清空等的初始 设定(S21)。

然后，在由结束判断部113判断并行执行的结束(S22：是)之前，为 步骤S23～S25的处理的重复。

如果接收部111接收到值和迭代号码i(th)(S23：是)，则保存控制 部112判断是否需要将暂定数据保存部104的值与迭代号码i的组通过接收 到的值和迭代号码i(th)覆盖(S24)。

该判断沿着图3的表进行。即，保存控制部112基于接收部111接收 到的迭代号码i(th)与保存在暂定数据保存部104中的迭代号码i的大小 关系进行判断。

即，如果迭代号码i不比迭代号码i(th)大(i＞i(th))，则保存控制 部112判断为不需要覆盖(S24：否)。

相对于此，如果迭代号码i是迭代号码i(th)以下(i≤i(th))，则保 存控制部112判断为需要覆盖(S24：是)。另外，在并行执行的刚开始后 的情况下等、在暂定数据保存部104中没有保存有数据时也判断为需要覆 盖。

并且，保存控制部112将接收到的值和迭代号码i(th)的组覆盖到暂 定数据保存部104中(S25)。

通过该覆盖，在保存控制部112中，迭代的顺序为顺序靠前的值被删 除，迭代的顺序为顺序更靠后的值被保存。

如果由结束判断部113判断为并行执行的结束(S22：是)，则确定部 114将暂定数据保存部104的值取出，反映给确定数据保存部105。

另外，在暂定数据保存部104的数据是无效的情况下(从多线程执行 部1个都没有发送数据的情况下、或发送的数据都是null的情况下等)，确 定部114也可以不进行值的取出。

根据以上那样的流程，通过在并行执行中重复的步骤S23～S25，保存 在暂定数据保存部104中的值成为在作为迭代的执行结果输出的多个值中 顺序最靠后的顺序的值。

因而，能够使与在并行执行的结束后逐次处理的情况相同的值反映到 确定数据保存部105中，能够实现终值保证。

并且，保存在暂定数据保存部104中的数据仅值和迭代号码的一个组 就足够，与按照线程准备存储器区域的情况相比能够成为较少的存储器区 域。

接着，举并行执行的具体例更详细地说明。

图4是表示实例程序1的图。该实例程序1的源代码表示进行a＝0，1， 2，3和4次的迭代。

在将该实例程序1逐次执行的情况下，因为

(1)a＝0时，由b[a]＝b[0]＝2＞-2，c＝0+1＝1

(2)a＝1时，由b[a]＝b[1]＝1＞-2，c＝1+1＝2

(3)a＝2时，由b[a]＝b[2]＝-1＞-2，c＝2+1＝3

(4)a＝3时，由b[a]＝b[3]＝-2≤-2，c不更新，所以为c＝3， 值“3”为处理结果。

假设将该实例程序1的4次的迭代划分而分配给各两次线程1(负责 a＝0，1)和线程2(负责a＝2，3)。

如图5所示，结束了第1个迭代(a＝0)的线程“1”将值1和迭代号 码“1”的组向数据更新管理部103的接收部111发送。

同样，线程1、2每当各次的迭代结束，就将该处理结果的值和迭代号 码的组向数据更新管理部103的接收部111发送。

考虑图5的4次的迭代以迭代号码1→3→2→4的顺序结束的情况。

将该情况下的各种数据的变迁的形象表示在图6、图7中。

如图6(a)所示，在第1个迭代结束时，多线程执行部向数据更新管 理部103发送作为迭代的执行结果的值“1”和迭代号码“1”。

如果数据更新管理部103的接收部111接收到该值“1”和迭代号码“1”， 则数据更新管理部103的保存控制部112因为在暂定数据保存部104中没 有保存有数据，所以判断为需要覆盖而进行覆盖(图2，S23：是，S24： 是，S25)。

如图6(b)所示，在第3个迭代结束时，数据更新管理部103的保存 控制部112因为保存在暂定数据保存部104中的迭代号码“1”是接收部111 接收到的迭代号码“3”以下，所以判断为需要覆盖而进行覆盖(S23：是， S24：是，S25)。

如图7(c)所示，在第2个迭代结束时，数据更新管理部103的保存 控制部112因为保存在暂定数据保存部104中的迭代号码“3”比接收部111 接收到的迭代号码“2”大，所以判断为不需要覆盖(S23：是，S24：否)。 并且，保存控制部112将接收部111接收到的值“2”和迭代号码“2”丢 弃。

如图7(d)所示，在第4个迭代结束时，数据更新管理部103的接收 部111接收到的值是“null”为空，所以保存控制部112判断为不需要覆盖 (S23：是，S24：否)。并且，保存控制部112将接收部111接收到的值“null” 和迭代号码“4”丢弃。

如图7(e)所示，全部的迭代结束，从多线程执行部102发送表示并 行执行的结束的结束信息，如果数据更新部103的结束判断部113接收到 该结束信息(S22：是)，则确定部114取得保存在暂定数据保存部104中 的值“3”，向确定数据保存部105保存(S26)。

这样，保存在确定数据保存部105中的值“3”与逐次处理时的处理结 果的值“3”(参照图4)一致，可知实现了终值保证。

(实施方式2)

实施方式2是在以循环处理的重复单位设定了用来将处理中中途中止 的断点的情况下也想要实现终值保证。

在这样设定了断点的情况下，在逐次执行时和并行执行时，执行的形 态不同，所以为了实现终值保证而需要进一步的设计。具体地使用图8进 行说明。

在图8(a)所示的实例程序2中，记述有包括4次的迭代的循环处理。

考虑将该程序逐次地执行。在该执行中，如果在第2个迭代中达到断 点，则不执行第3个、第4个迭代(图8(b))。

这里，假设将该实例程序2的4次迭代如图8(c)所示那样对线程1 和线程2各分配两次。

如上所述，在逐次执行的情况下，不执行第3个、第4个迭代，所以 在并行执行的情况下，也需要使得第3个、第4个迭代的处理结果不作为 一系列的处理的最终的值反映。

所以，在本实施方式2中，通过利用表示是否到达了断点的中断标志 (是在到达时为ON、在未到达时为OFF的标志)，实现终值保证的实现。

如图9所示，多线程并行执行装置901具备多线程执行部902、数据更 新管理部903、暂定数据保存部904。

多线程执行部902每当各线程中的迭代结束，将表示迭代的执行结果 的值、表示执行的迭代在循环处理中是第几个的迭代号码i(th)、以及表 示是否到达了断点的中断标志的组向接收部911发送。其他功能与多线程 执行部102(图1)是同样的。

数据更新管理部903的保存控制部912基于接收部911接收到的值、 迭代号码i(th)和中断标志的三者的组，进行是否覆盖保存的控制。

暂定数据保存部904是用来在由多线程执行部902进行的并行执行中 保存值、迭代号码i和中断标志的三者的组的单元。

图9的其他功能块与使用图1说明的功能块是同样的，所以省略说明。

接着，参照图10对多线程并行执行时的数据更新管理部903的动作进 行说明。

在图10中，赋予了与图2相同的号码的步骤S21～S22、S26与图2 是同样的，所以省略说明。

特别是，如果接收部911接收到值、迭代号码i(th)和中断标志的组 (S103：是)，则保存控制部912判断是否需要将暂定数据保存部904的值、 迭代号码i和中断标志通过接收到的值、迭代号码i(th)和中断标志覆盖 (S104)。

该判断沿着图11的表。

如图11的表所示，基于接收部911接收到的中断标志的ON/OFF、保 存在暂定数据保存部904中的中断标志的ON/OFF、迭代号码的大小关系 的3个要素，保存控制部912判断覆盖还是不覆盖。

以下，对在图11的表中、在L1～L6的各行中使覆盖的有无不同的理 由简单地说明。

L1～L2的行与实施方式1同样，将迭代号码在顺序上更靠后的值保存 到暂定数据保存部904中。

L3的行由于在暂定数据保存部904中已保存有中断的值，所以不覆盖。

L4的行由于接收部911接收到的值是中断的值，所以进行覆盖。

L5、L6的行是在多个迭代中、在2以上的迭代中到达了断点的情况。 此时，在暂定数据保存部104中，需要保留与向断点最初(在假定为逐次 处理的情况下的顺序中为最初)到达的迭代对应的值。

因而，在L5的行中，如果接收部911接收到的迭代号码i(th)比保 存在暂定数据保存部904中的迭代号码i顺序靠前，则进行覆盖。L6的行 为L5的行的相反。

保存控制部912按照图11的表，如果判断为需要覆盖(S104：是)， 则将接收到的值、迭代号码i(th)和中断标志的组覆盖到暂定数据保存部 904中(S105)。

然后，在通过结束判断部113判断并行执行的结束(S22：是)之前， 为步骤S103、S104、S105的处理的重复。

并且，如果由结束判断部113判断为并行执行的结束(S22：是)，则 确定部114将保存在暂定数据保存部904中的值向确定数据保存部105反 映(S26)。

此时，保存在暂定数据保存部904中的值保存着与在假设为逐次处理 的情况下的顺序中向断点最初到达的迭代对应的值，所以能够实现终值保 证。

(实施方式3)

实施方式3是将实施方式1的数据更新管理部103作为多线程执行部 内的管理线程构成的。

如图12所示，多线程并行执行装置1201具备多线程执行部1202。该 多线程执行部1202包括分担处理循环处理的迭代的处理线程1202a、 1202b、和数据更新管理线程1203。

数据更新管理线程1203具备与数据更新管理部103(图1)同样的功 能。

即，数据更新管理线程1203具备以下的(1)～(4)的功能。

(1)从处理线程1202a、1202b接收包括表示迭代的执行结果的值、 和表示已执行的迭代在循环处理中是第几个的迭代号码i(th)的组的信息 的功能(对应于图1：接收部111的功能)。

(2)基于接收到的信息、进行是否覆盖保存到暂定数据保存部104中 的控制的功能(对应于图1：保存控制部112的功能)。

(3)如果从处理线程1202a、1202b接收表示并行执行的结束的结束 信息、则判断并行执行的结束的功能(对应于图1：结束判断部113的功能)。

(4)如果判断为并行执行的结束、则将保存在暂定数据保存部104中 的值取出、向确定数据保存部105反映的功能(对应于图1：确定部114 的功能)。

另外，也可以构成为，使得在数据更新管理线程1203中具备在实施方 式2中说明的数据更新管理部903(图9)的功能。

(实施方式4)

在实施方式4中，对从源程序生成面向处理线程及数据更新管理线程 的程序的多线程编译器进行说明。

图13是多线程编译器1302的结构图。

在图13中，多线程编译器1302以源程序1301为输入，生成处理线程 程序1310、数据更新管理线程程序1311。

前处理部1303对源程序1301执行循环优化等的前处理。

处理线程程序生成部1304在能够并行处理的循环处理及循环内从多个 处理线程导出代入的变量，生成作为数据更新管理线程的管理对象的管理 对象变量列表1305及附加了并行化处理和向数据更新管理线程的通知处理 的处理线程程序的中间代码1306。

数据更新管理线程程序生成部1307生成用来对管理对象变量列表 1305的各变量进行图2所示的流程图的动作的、数据更新管理线程程序的 中间代码1308。

后处理部1309对处理线程程序的中间代码1306及数据更新管理线程 程序的中间代码1308执行代码变换等的后处理。

图14是处理线程程序生成部1304的流程图。

在图14中，处理线程程序生成部首先判断是否有未解析的循环处理 (S1401)。

在没有未解析的循环处理的情况下(S1401：否)，结束处理。

在有未解析的循环处理的情况下(S1401：是)，判断在该循环的迭代 间是否有依存关系(S1402)。

在循环的迭代间有依存关系的情况下(S1402：有)，回到是否有未解 析的循环处理的判断(S1401)。

在循环的迭代间没有依存关系的情况下(S1402：无)，判断是否有未 解析的循环内代入变量(S1403)。

在没有未解析的循环内代入变量的情况下(S1403：否)，向并行处理 开始、结束处理的附加(S1408)前进。

在有未解析的循环内代入变量的情况下(S1403：是)，进行以下的处 理。

在该变量被循环外参照的情况下(S1404：是)，附加用来对数据更新 管理线程通知的线程数据更新信息的通知处理(S1405)。

这里所述的“线程数据更新信息”，是有关各处理线程处理的数据的更 新的信息。例如，包括表示迭代的执行结果的值和迭代号码i(th)的组。

在该变量被循环内参照的情况下(S1406：是)，将上述变量复制为处 理线程内专用(S1407)。

接着，附加并行处理开始处理及结束处理(S1408)，回到是否有未解 析的循环处理的判断(S1401)。

根据该结构，数据更新管理线程接收来自各处理线程的线程数据更新 信息，进行是否更新数据更新信息的判断，将终值保证所不需要的数据丢 弃，仅保存需要的1个数据，因此，不需要按照处理线程保存数据更新信 息的区域，所以能够通过少量的存储器区域实现多线程并行执行时的终值 保证。

此外，通过在多线程执行机构之上执行数据更新管理线程，能够使用 已有的多线程执行机构实现。此外，通过多线程编译器，能够从在1个线 程中动作的程序自动地生成能够在多线程执行机构上动作、实现了终值保 证的程序。

另外，多线程编译器1302生成的处理线程程序1310既可以是1个程 序，也可以由多个程序构成。

另外，处理线程程序1310及数据更新管理线程程序1311既可以是与 源程序相同的语言的程序，也可以是在多线程动作机构上动作的对象代码。

另外，在本实施方式4中，生成管理对象变量列表1305、处理线程程 序的中间代码1306、及数据更新管理线程程序的中间代码1308，但也可以 生成为文件等，也可以仅在编译器内部中保持信息。

此外，在本实施方式4中，将前处理部1303与其他处理部分开表示， 但也可以考虑没有前处理部1303的结构。此外，也可以采取前处理部1303 包含在其他处理部中的结构。

另外，在本实施方式4中，将后处理部1309与其他处理部分开表示， 但也可以考虑没有后处理部1309的结构。此外，也可以采取后处理部1309 包含在其他处理部中的结构。

(实施方式5)

实施方式5是将在实施方式1等中说明的多线程并行执行装置用集成 电路(LSI)构成的。该集成电路可以搭载在数字电视机或蓝光记录机等的 各种AV设备中。

如图15所示，集成电路1501具备多线程执行部1202和暂定数据保存 部104。

另外，集成电路例如是LSI，既可以单独1芯片化，也可以包括一部分 或全部而1芯片化。这里设为LSI，但根据集成度的差异，也有称作IC、 系统LSI、超级LSI、超大规模LSI的情况。此外，集成电路化的方法并不 限定于LSI，也可以通过专用电路或通用处理器实现。也可以使用在LSI 制造后能够编程的FPGA(Field Programmable Gate Array)、或能够再构成 LSI内部的电路单元的连接及设定的可重构处理器。进而，如果因半导体技 术的进步或派生的其他技术出现代替LSI的集成电路化的技术，则当然也 可以使用该技术进行功能块的集成化。

(实施方式6)

在实施方式1中说明的多线程并行执行装置装入在各种装置中，适当 地执行解码及再编码。

图16所示的广播流再现装置1601具备接收广播流的接收部1602、将 接收到的广播流解码的解码部1603、将解码后的广播流再现的再现部1604。 该解码部1603包括多线程并行执行装置101而构成。

图17所示的广播流储存装置1701具备接收广播流的接收部1602、将 接收到的广播流再编码的再编码部1705、将再编码后的广播流储存的储存 部1706。该再编码部1705包括多线程并行执行装置101而构成。

图18所示的储存流再现装置1801保存储存流的储存部1706、将储存 的流解码的解码部1603、将解码后的流再现的再现部1604。该解码部1603 包括多线程并行执行装置101而构成。

图19所示的储存流再编码装置1901具备储存流的储存部1706、将储 存的流再编码的再编码部1705。该再编码部1705包括多线程并行执行装置 101而构成。

另外，本实施方式6可以与各实施方式适当组合。例如，也可以将在 实施方式5中说明的集成电路1501装入到广播流再现装置1601中。

(实施方式7)

在实施方式1中，暂定数据保存部104保存的信息是表示迭代的执行 结果的值和迭代号码i的1组，但也可以将这些组保存多个。

通过这样保存多个组，在将多个种类的迭代并行执行的情况下也能够 实现终值保证。

使用图22说明一例。多线程并行执行装置2201具备多线程执行部 2202、数据更新管理部2203、暂定数据保存部2204。

暂定数据保存部2204分别保存有n个(n是2以上的整数)由(1)表 示迭代的执行结果的值、(2)迭代号码i、(3)用来识别迭代的种类的识别 ID的三者构成的组。

多线程执行部2202具有将多个种类的迭代并行执行的功能，每当各线 程中的迭代结束，将表示迭代的执行结果的值、迭代号码i、及识别ID向 接收部2211发送。

此外，多线程执行部2202如果多个种类中的某个的全部迭代结束，则 将包括用来识别结束的迭代的种类的识别ID的结束信息向结束判断部 2213发送。

保存控制部2212如果接收部2211接收到值、迭代号码i和识别ID的 三者的组，则基于接收到的迭代号码i、和与在暂定数据保存部2204中接 收到的识别ID对应的迭代号码i的大小关系，进行是否将对应于该识别ID 的值及迭代号码i覆盖保存的控制。

保存控制部2212在覆盖保存时，从暂定数据保存部2204保存的信息 之中，将对应于识别ID的值及迭代号码i作为覆盖的对象。

结束判断部2213如果从多线程执行部2202接收到上述结束信息，则 确定部2214从保存在暂定数据保存部2204中的组之中取得与包含在该结 束信息中的识别ID对应的值，保存到确定数据保存部2205中。

另外，为了区别是哪个种类的迭代的处理结果，也可以在确定数据保 存部2205中将识别ID与值建立关联而保存。

以上对本实施方式7进行了说明，但也可以考虑使用在实施方式2中 说明的中断标志的变形例。作为具体的结构，多线程执行部2202每当各线 程中的迭代结束，将(1)表示迭代的执行结果的值、(2)表示已执行的迭 代在循环处理中是第几个的迭代号码i(th)、(3)用来识别迭代的种类的 识别ID、(4)表示是否到达了断点的中断标志的4种信息向接收部2211 发送。并且，保存控制部2212基于接收到的迭代号码i与在暂定数据保存 部2204中对应于接收到的识别ID的迭代号码i的大小关系、以及接收到 的中断标志的ON/OFF和与在暂定数据保存部2204中接收到的识别ID对 应的中断标志的ON/OFF，进行覆盖保存的有无的判断。该判断的方法与 使用图11说明的是同样的，所以省略说明。

(实施方式8)

也可以在各实施方式中说明的多线程执行部发出的命令中包括在以下 的(1)～(3)中说明那样的内容。这些命令能够贡献于柔性的并行执行。 基本的结构与在图1中说明的是同样的，所以在以下的本实施方式的说明 中使用图1的功能块进行。

(1)将暂定数据保存部104的信息无效化的命令

从多线程执行部102经由接收部111接受到该命令的保存控制部112 将暂定数据保存部104的信息无效化(或者清空)。该命令可以用于多线程 并行执行的初始设定(图2，S21)等。

(2)对管理硬件发送线程数据更新信息的命令

是将线程数据更新信息(有关各处理线程处理的数据的更新的信息) 向管理硬件发送的命令。

(3)将暂定数据保存部104的信息反映到实际的变量中的命令

是将暂定数据保存部104的信息保存到确定数据保存部105中而反映 到实际的变量中的命令。该命令例如可以在值的反映处理(图2，S26)中 使用。

(实施方式9)

本实施方式9是将实施方式7、8混合那样的实施方式。在以下的说明 中使用图22的功能块进行。

在实施方式9中，与实施方式7同样，暂定数据保存部2204分别保存 有n个(n是2以上的整数)由(1)表示迭代的执行结果的值、(2)迭代 号码i、(3)识别ID的三者构成的组。

并且，在多线程执行部2202的线程数据更新信息中，包括用来确定是 该n个的组的中的哪个的识别ID。

此外，在多线程执行部2202中，也可以发出以下这样的命令。下述(1)～ (3)的哪个都包括用来识别命令的执行对象的1个以上的识别ID。

(1)将暂定数据保存部2204的区域确保或无效化的命令

是将暂定数据保存部2204内的对应于识别ID用的区域确保或无效化 的命令。这些命令可以用于多线程并行执行的初始设定(图2，S21)。

此外，在不能确保(无效化)的情况下，可以考虑将发生例外处理、 或管理各区域的占用状态的状态寄存器更新。

(2)将线程数据更新信息向管理硬件发送的命令

是将对应于指定的识别ID的线程数据更新信息向管理硬件发送的命 令。

(3)将暂定数据保存部2204的信息反映到实际的变量中的命令

是将对应于指定的识别ID的暂定数据保存部2204的信息保存到确定 数据保存部2205中而反映到实际的变量中的命令。该命令例如可以在值的 反映处理(图2，S26)中使用。

(4)将暂定数据保存部2204的区域释放的命令

是将暂定数据保存部2204内的对应于1个以上的识别ID用的区域释 放的命令。该命令例如可以将经过值的反映处理(图2，S26)、没有用的 区域用在对象中。

此外，也可以将有关上述(3)及(4)的处理通过1个命令实现。

<补充1>

以上，对本实施方式进行了说明，但本发明并不限定于上述内容，在 用来达到本发明的目的和与其关联或附属的目的的各种形态中也能够实 施，例如也可以是以下这样。

(1)在实施方式中，如图5所示，设在没有更新值的迭代的情况下， 多线程执行部102发送表示数据是空的“null”而进行了说明，但并不限定 于此。例如，关于不更新值的迭代，多线程执行部102也可以不发送值或 迭代号码。

(2)在实施方式中，如图1那样，将暂定数据保存部104和确定数据 保存部105表示为不同的保存机构，但也可以是相同的数据保存机构。

(3)在实施方式中，如图4那样举出了使for～if文的命令重复的例 子进行了说明，但并不限定于此。例如在C语言中，也可以使用for语句、 while语句、do while语句等。

(4)在实施方式中，每当各迭代结束，多线程执行部102将作为其执 行结果的值和迭代号码发送，但也可以代替它而以线程的结束为契机发送。

例如，如图20(a)所示，如果线程1的处理结束，则多线程执行部 102发送表示线程1负责的迭代的执行结果的值“2”和线程号码“th1”。

同样，如果线程2的处理结束，则多线程执行部102发送表示线程2 负责的迭代的执行结果的值“3”和线程号码“th2”。

并且，数据更新部管理部103的保存控制部112基于线程号码的大小 关系判断覆盖的需要与否。

在图20(b)的例子中，由于保存在暂定数据保存部中的线程号码“th2” 比接收到的线程号码“th1”顺序靠后，所以不覆盖。

(5)在实施方式中，如图2所示，关于初始设定(S21)停留在简单 的说明，但例如也可以如以下这样进行对应于数据更新的有无的行为。

即，如图21所示，作为初始设定，保存控制部112将迭代号码设定为 “-1”(S2101)。

并且，在并行执行结束后(S22：是)，保存控制部112如果迭代号码 是“-1”的原状(S2102：否)，则意味着暂定数据保存部104的值尽管有 并行执行也没有被更新，所以将数据的反映(S26)跳过。

(6)在实施方式中，如图7(e)所示，在并行执行的结束时使保存在 暂定数据保存部104中的值为“3”、向确定数据保存部105反映，但并不 限定于此。

总之只要能够确定值“3”作为并行执行的结果就可以。例如，也可以 将表示是结果的信息附加给值“3”。

(7)各在实施方式中，设多线程执行部中的处理线程数为两个而进行 了说明，但并不限定于此，只要是两个以上，可以取任意的个数。

例如，处理线程数也可以是4个或8个。

(8)也可以将实施方式1～9及本补充的内容组合实施。

<补充2>

本实施方式包括以下的形态。

(1)有关本实施方式的多线程并行执行装置，其特征在于，具备：执 行机构，将一个循环处理中的重复单位分为多个线程并行执行；接收机构， 在上述执行机构并行执行的期间中，从上述执行机构接收表示各线程中的 重复单位的执行的结果的值、和表示该重复单位的顺序的顺序信息的组； 保存机构，用来保存上述值和上述顺序信息的组；控制机构，在上述接收 机构接收到上述组的情况下，基于由接收到的上述顺序信息与保存在上述 保存部中的顺序信息分别表示的顺序的先后，控制是使接收到的上述顺序 信息和对应的上述值的组覆盖还是不覆盖到上述保存部中；确定机构，如 果由上述执行机构进行的并行执行结束，则确定保存在上述保存机构中的 值作为上述一个循环处理的执行结果。

(2)也可以是，在上述一个循环处理中的重复单位中，设定了用来将 处理在中途中止的断点；上述接收机构接收的上述组除了上述值和上述顺 序信息以外，还包括表示向上述断点已到达还是未到达的标志；上述保存 机构是用来保存包括上述值、上述顺序信息和上述标志的组的；上述控制 机构将包含在由上述接收机构接收到的上述组中的上述顺序信息和上述标 志参照保存在上述保存机构中的上述顺序信息和上述标志，进行上述覆盖 的控制。

根据该结构，在设定了断点的循环处理中也能够实现终值保证。

(3)也可以是，上述控制机构如果与在假设将上述一个循环处理逐次 处理的情况下向断点最初到达的重复单位对应的值保存在上述保存机构 中，则抑制上述覆盖。

(4)也可以是，上述控制机构在有由上述接收机构进行的接收的情况 下，当接收到的上述顺序信息表示比保存在上述保存部中的顺序信息顺序 靠后时，使接收到的上述值和上述顺序信息的组覆盖到上述保存部中，当 接收到的上述顺序信息表示比保存在上述保存部中的顺序信息顺序靠前 时，使接收到的上述值和上述顺序信息的组不覆盖到上述保存部中。

(5)也可以是，上述一个循环处理中的重复单位是迭代；上述顺序信 息是表示迭代的顺序的迭代号码。

(6)也可以是，上述接收机构、上述控制机构及上述确定机构由作为 上述执行机构的执行对象的管理线程构成。

(7)也可以是，上述执行机构并行执行的重复单位有多个种类；上述 接收机构除了上述组以外还接收用来识别上述重复单位的种类的识别码； 上述保存机构与用来识别重复单位的种类的识别码建立关联而保存上述 组；上述控制机构以与接收到的识别码建立了关联的组为对象进行覆盖的 有无的控制。

(8)也可以是，上述执行机构发出将上述保存机构保存的信息无效化 的命令、将上述组向管理用硬件发送的命令、或者将保存在上述保存机构 中的值反映到实际的变量中的命令的至少某1个命令。

(9)在(8)中，也可以是，上述执行机构并行执行的重复单位有多 个种类；上述接收机构除了上述组以外还接收用来识别上述重复单位的种 类的识别码；上述保存机构与用来识别重复单位的种类的识别码建立关联 而保存上述组；上述控制机构是以与接收到的识别码建立了关联的组为对 象进行覆盖的有无的控制的；上述执行机构发出的命令包括作为执行对象 的识别码。

(10)广播流再现装置也可以是，具备：接收机构，接收广播流；解 码机构，将接收到的广播流解码；再现机构，将解码后的广播流再现；上 述解码机构包括(1)的多线程并行执行装置而构成。

(11)广播流储存装置也可以是，具备：接收机构，接收广播流；再 编码机构，将接收到的广播流再编码；储存机构，将再编码后的广播流储 存；上述再编码机构包括(1)的多线程并行执行装置而构成。

(12)储存流再现装置也可以是，具备：储存机构，储存流；解码机 构，将储存的流解码；再现机构，将解码后的流再现；上述解码机构包括 (1)的多线程并行执行装置而构成。

(13)储存流再编码装置也可以是，具备：储存机构，储存流；再编 码机构，将储存的流再编码；上述再编码机构包括(1)的多线程并行执行 装置而构成。

(14)一种集成电路，其特征在于，具备：执行机构，将一个循环处 理中的重复单位分为多个线程并行执行；接收机构，在上述执行机构并行 执行的期间中，从上述执行机构接收表示各线程中的重复单位的执行的结 果的值、和表示该重复单位的顺序的顺序信息的组；保存机构，用来保存 上述值和上述顺序信息的组；控制机构，在上述接收机构接收到上述组的 情况下，基于由接收到的上述顺序信息与保存在上述保存部中的顺序信息 分别表示的顺序的先后，控制是使接收到的上述顺序信息和对应的上述值 的组覆盖还是不覆盖到上述保存部中；确定机构，如果由上述执行机构进 行的并行执行结束，则确定保存在上述保存机构中的值作为上述一个循环 处理的执行结果。

(15)上述执行机构也可以由多线程处理器构成。

(16)上述执行机构也可以由多核处理器构成。

(17)有关本实施方式的多线程并行执行方法，其特征在于，包括： 执行步骤，将一个循环处理中的重复单位分为多个线程使执行机构并行执 行；接收步骤，在上述执行步骤中上述执行机构并行执行的期间中，从上 述执行机构接收表示各线程中的重复单位的执行的结果的值、和表示该重 复单位的顺序的顺序信息的组；保存步骤，用来将上述值和上述顺序信息 的组保存到保存机构中；控制步骤，在上述接收步骤接收到上述组的情况 下，基于由接收到的上述顺序信息与保存在上述保存机构中的顺序信息分 别表示的顺序的先后，控制是使接收到的上述顺序信息和对应的上述值的 组覆盖还是不覆盖到上述保存机构中；确定步骤，如果上述执行步骤中的 并行执行结束，则确定保存在上述保存机构中的值作为上述一个循环处理 的执行结果。

(18)有关本实施方式的多线程编译器，是将在1个处理线程上动作 而包括循环处理的源程序编译的多线程编译器，其特征在于，生成：多个 处理线程用的程序，每当上述循环处理中的重复单位结束，则将表示执行 的结果的值和表示该重复单位的顺序的顺序信息的组发送；数据更新管理 线程用的程序，如果从各处理线程接收到上述组，则将包含在该组中的顺 序信息与在保存机构中已经保存的顺序信息比较，控制将包含在接收到的 组中的值和顺序信息覆盖还是不覆盖到上述保存机构中。

工业实用性

有关本发明的多线程并行执行装置在将一个循环处理中的重复单位分 为多个线程而并行执行那样的多线程执行环境中具有实用性。

标号说明

101、901、1201、2201 多线程并行执行装置

102、902、1202、2202 多线程执行部

103、903、2203 数据更新管理部

104、904、2204 暂定数据保存部

105、2205 确定数据保存部

111、911、2211 接收部

112、912、2212 保存控制部

113、2213 结束判断部

114、2214 确定部

1202a、1202b 处理线程

1203 数据更新管理线程

1302 多线程编译器

1501 集成电路

1601 广播流再现装置

1602 接收部

1603 解码部

1604 再现部

1701 广播流储存装置

1705 再编码部

1706 储存部

1801 储存流再现装置

1901 储存流再编码装置