2011 英特尔® 线程挑战赛 —Parallelized Parser and Formula Interpreter

作者： 邓辉 (9 篇文章) 日期： 八月 9, 2011 在 2:43 下午

 

2011 英特尔® 线程挑战赛—

并行语法分析器与公式解释器

邓辉   denghui0815@hotmail.com

由于时间关系，文档写的不是太仔细，抱歉!

 源码下载

问题描述

公式语法分析器和解释器分析连续的输入文字流，检查语法是否正确，根据输入内容分析出其数据结构并解析公式。公式的结果可以存储在变量中，将来的公式可以使用所有未作为公式的某个值从内存中除去的变量。最新多核硬件中的并行处理功能可用于增加语法分析器和解释器的吞吐量。许多热门 Web 浏览器的 JavaScript 引擎中的最新增强功能都需要提高与网络相关的语法分析器的处理速度。

问题描述：

编写一段多线程代码，解释、执行输入语句并生成输出结果。发送到输出结果的文字顺序应与程序输入语句中的顺序一致。您可以并行执行多个语句以增加吞吐量。

注意：关键字和变量区分大小写。行结束符为分号 (;)

下面的示例定义了两行：

var x = 50;

var y = 10;

有效关键字和函数：

关键字 描述 示例
var {variableName} 定义一个名为 variableName 的新变量。variableName 可由字母和数字 [A-Za-z0-9] 组成，但必须以字母开头。数据类型必须由程序根据使用赋值运算符 (=) 赋予变量的值来判断。 var x = 50;var double = 50.2353;var decimal = 345.212312321;
free(variableName) 释放变量占用的内存。通过使用 var 关键字再次定义变量名称，可以复用该变量名称。如果某个语句尝试使用已释放的变量，程序应停止执行，并显示错误消息指出导致发生“变量未定义”错误的行号和语句。 free(x);
string(variableName | value) 将指定为参数的值或变量转换为其字符串表示。转换时应始终在十进制小数点后使用固定数量的十位数字。例如，string(50.323467); 应求值为 50.3234670000。不进行任何舍入处理，仅在需要时截断和添加 0。 string(3450.212);string(double);string(result);
output(variableName | value) 将指定为参数的值或变量发送到输出缓冲区/文件。如果参数是一个数字，解释器应使用为字符串函数指定的相同机制将其转换为字符串。例如，output(50.323467) 应将 50.3234670000 发送到输出结果中。 ouput(325.30);output(25 + 32);output(result);

output(result + 32);

output(string(20) + string(70));

注意：公式可以用作参数，而公式结果应为该参数的值。为方便起见，您可以将语法分析器类型映射为许多高级语言中定义的标准类型，例如有符号整数、有符号双精度和字符串（允许的最大长度为 256 个字符）等数字类型。

示例：

output(50 + 20);

string(35 + 32);

string(32 * 12 * multiplier);

使用 var 关键字定义变量后，可以不用关键字将新值赋予该变量。例如：

var a = 50;

a = a + 1;

a = 30;

free(a);

数字以及数字变量的有效算术运算符：

运算符 描述 示例
= 基本赋值 var x = 50;var double = 50.2353;var decimal = 345.212312321;
+ 加法 var z = x + double;var q = y + z;output((30 + 20) + 10);
- 减法 var z = q - d;var result = (30 - 16);
* 乘法 var m = 30 * 5;var z = (30 + 5) * 2;
/ 除法 — 实型数据 var div = (30 / 2);var d = 5 / 2;var m = ((50 * d) / div) + 25;

注意：语法分析器将支持从整数到双精度数据类型的隐式转换。

圆括号用于将表达式分组以控制执行顺序。

例如：

var m = ((50 * d) / div) + 25;

应按以下步骤解析：

 (50 * d)

(上一个运算的结果) / div

(上一个运算的结果) + 25

字符串括在双引号 (") 内 — ASCII 码 34、" 或 "

字符串的有效运算符：

运算符 描述 示例
= 基本赋值 var str = "String Value";var str2 = str + " and more";var str3 = string(35 + 12);

var str4 = "result: " + string(50 / 2);

str4 = str4 + "a";

str = str + str4;
{string} + {string} 连接 var strConcat = str1 + str2 + str3;output("First result: " + string(result));

注意：不允许使用 {string} + {number} 连接。需要使用 string({number}) 将数字转换为字符串。关键字和例程名称对于变量名称无效。如果发生语法错误，程序应停止执行并显示错误消息指出导致发生语法错误的行号和语句。

有效数学例程/函数：

函数 描述 示例
pow(variableName | value, variableName | value) 返回底数（第一个参数）的指数（第二个参数）次方 var result = pow(2, 4);var powRes = pow(20 + 5, (6 / res));
sqrt(variableName | value) 返回参数的平方根。如果数字为负数，应显示错误消息并停止执行，因为这属于语法错误。 var result = sqrt(1400);output("srq: " + string(sqrt(30)));</t

输入描述：

此程序的输入内容来自命令行上指定的一个文本文件（此文件名作为程序的第一个参数）。文件结束标志着待执行语句的结束。如上所述，解释器可以决定用来解释输入文件中所有语句的最佳机制并生成输出结果。

输出描述：

该程序将解释输入文件中的每个输出函数并为其输出一行。输出内容应包含调用结果，并且输出顺序与输入文件中一致。保证输出结果正确无误最为重要，但高吞吐量和可扩展性作为评分考量因素也很重要。程序的输出结果将储存在命令行上作为第二个参数指定的文本文件中。如果出现语法错误，应按照前面的说明将相应消息写入到输出文件中。

命令行示例： formulaint.exe input.txt output.txt

输入示例文件，input.txt：

var a = 150;

var b = 320;

var c = (a + b) / 20;

var d = ((320 / 2) * 50);

output("Value for a: " + string(a));

output("Value for b: " + string(b)); var message = "a / b = ";

message = message + string(a / b);

var unusedStr = "I will not use this string at all. Will you waste memory on me?";

output(message);

free(message);

free(unusedStr);

free(a);

free(b);

free(c);

free(d);

输出示例文件，output.txt：

Value for a: 150.0000000000

Value for b: 320.0000000000

a / b = 0.4687500000

计时：将使用此程序的总执行时间进行计分。为得到最准确的计时结果，所提交的代码需要包含计时代码并将计算出的总执行时间打印到标准输出，否则将使用外部秒表计时。

串行算法

解释器首先需要完成的功能是分词，分词规则如下：

1.     关键字： var sqrt pow string free output

2.     运算符号： = + - * / ( )；

3.     数字；    

4.     字符串；

5.     变量名；

6.     语句结束符号 ;

7.     分割符号 空格 \t \r \n

而语法分析器需要支持四种语法：

1.     变量定义语句：   var 变量名 = 表达式；

2.     变量赋值语句：   变量名 = 表达式；

3.     变量释放语句：   free（变量名）；

4.     输出语句：       output（表达式）；

在语法解析时将表达式转换为逆波兰表达式。

转换方法

1.     首先构造一个运算符栈，此运算符在栈内遵循越往栈顶优先级越高的原则。

2.     读入一个用中缀表示的简单算术表达式，为方便起见,设该简单算术表达式的右端多加上了优先级最低的特殊符号“#”。

3.     从左至右扫描该算术表达式，从第一个字符开始判断，如果该字符是数字，则分析到该数字串的结束并将该数字串直接输出。

4.     如果不是数字，该字符则是运算符，此时需比较优先关系。

做法如下：将该字符与运算符栈顶的运算符的优先关系相比较。如果，该字符优先关系高于此运算符栈顶的运算符，则将该运算符入栈。倘若不是的话，则将栈顶的运算符从栈中弹出，直到栈顶运算符的优先级低于当前运算符，将该字符入栈。

5.     重复上述操作(3)-(4)直至扫描完整个简单算术表达式，确定所有字符都得到正确处理，我们便可以将中缀式表示的简单算术表达式转化为逆波兰表示的简单算术表达式。

例如：

        a =  ( (b + c) * pow(d, e));

                   变量           运算符                   表达式

a                                       a

a               =                       a

a b             =                       a b

a b             = +                     a b

a b c           = +                     a b c

a b c           =                       a b c +

a b c           = *                     a b c +

a b c           = * pow                 a b c +

a b c d         = * pow                 a b c + d

a b c d e       = * pow                 a b c + d e

a b c d e       = *                     a b c + d e pow

a b c d e       =                       a b c + d e pow *

a b c d e       =                       a b c + d e pow * =

最后是对表达式求值。

热点分析

使用Intel Amplifier分析热点，结果如下：

结果表明，表达式求值函数与变量取值函数占用的时间较大。

并行算法

由于表达式包含输入和输出，如果表达式的输入没有交集时，这些表达式可以并行求值。所以可以分析表达式的输入，根据依赖关系激活表达式，已求值的表达式输出更新未求值表达式的输入。当一个未求值的表达式所有输入均已更新，则将其加入到待求职表达式队列中。利用多个线程并行对待求值表达式的求值运算。        

使用Intel Amplifier分析Concurrency，结果如下：

分类： 博客征文专栏, 并行计算, 开放源代码
标签：, ,

如需了解英特尔软件产品相关的性能和优化选项，请参阅优化注意事项.

 评论 (0)

 引用 (0)


 写评论  

欲获得技术支持，请访问软件支持页面.
姓名 (必填)*

电子邮件 (必填，不在本页面显示)*

您的 URL (可选)


评论*