[发明专利]一种数据容错的多线程投机方法

摘要

本发明公开一种数据容错的多线程投机方法。该方法是基于数据容错的多线程投机方法，让先到达栅栏的线程投机执行，充分利用众多线程之间同步数据造成的运行时间浪费，加速程序运行。本发明基于投机，判断，回滚的流程通过回滚错误的投机来保证程序的正确性。本发明对投机判断和回滚判断进行了建模，保证其效率。本发明通过限制投机深度，使得投机收益在减去该投机开销后保持一定范围内的稳定，从而提供稳定的程序运行速度提升。

主权项

一种数据容错的多线程投机方法，其特征在于该方法包括以下步骤：步骤(1)、线程到达栅栏，赋予投机线程容错数据版本：多线程执行过程中线程会遇到多个栅栏，对于任何先于其他线程到达某一栅栏的线程，从第一个穿越该栅栏的线程开始，每个线程所携带的容错数据赋予一个版本，该版本的赋予由其穿越该栅栏的次序决定；最后一个到达该栅栏的线程拥有数据的最终版本，所述的最终版本为数据的正确版本；对于先于其他到达栅栏的线程，允许其携带自身的数据继续执行而不是等待其他线程，其携带的数据称为容错数据，该带有容错数据的线程称为容错投机线程；步骤(2)、判断投机线程容错数据版本是否为最终版本：当某个投机线程到达栅栏时，判断其容错数据版本是否为最终版本；若不是最终版本，则该线程继续投机执行步骤(3)；反之则标记自身为非投机线程正确运行并发出投机唤醒信号，通知非最终版本的投机线程执行步骤(5)；步骤(3)、判断非最终版本的投机线程是否收到收到投机唤醒信号，若收到则执行步骤(5)，否则执行步骤(4)；步骤(4)、判断投机线程是否需要回滚：对于非最终版本的投机线程，在其每到下一个栅栏时都要判断其是否需要回滚，判断线程回滚条件如下所述；如果不需要回滚，则继续投机执行；如果需要回滚，则回滚至该投机线程第一次投机执行所在的栅栏；所述的线程回滚的条件为：投机线程在最终版本的数据到达之前，若该线程已经投机执行超过了设定的投机深度，则回滚；所述的投机深度为允许投机线程携带容错数据穿越的栅栏数目；步骤(5)、判断投机线程是否投机成功：对于非最终版本的投机线程，在收到投机唤醒信号后都要判断自身是否投机成功，投机成功的判断条件如下所述；如果投机成功，则标记自身为非投机线程正确运行；反之则回滚至该投机线程第一次投机执行时所在的栅栏；所述的投机成功条件为：投机线程内的容错数据与最终版本的数据相同；或者投机线程内的容错数据与最终版本的数据不相同，但该投机线程最终的运行结果与容错数据无关。