在Real-time中使用并行和SignalR解决莎士比亚的“百万猴子”问题

在Real-time中使用并行和SignalR解决莎士比亚的“百万猴子”问题

  • Comments 0

[原文发表地址]  Solving the Shakespeare Million Monkeys Problem in Real-time with Parallelism and SignalR

[原文发表时间]  2011-11-12  01:09

大约18个月前我跟Stephen Toub(在并行计算方面享有盛名)谈论过并行,以及它可以解决的问题。

A monkey with a skull. Oh yes.我天真地问:“我们可以解决百万猴子的问题吗?”

他说:“这是什么问题?”

“你知道,如果你有无限只猴子,还有无限个键盘,它们就能写出莎士比亚的作品。”

我们对一些想法做了下头脑风暴(因为Steven比我聪明些,所以整个头脑风暴中,他总是若有所思地凝视着空气,而我则坐在那儿什么都不干。)最后,我们决定用遗传算法。我们每秒会培育上千品种(假定的)猴子,然后根据他们写出莎士比亚作品的能力来选定哪几种可以被保留。

我们用.NET 4任务并行库让算法能更容易扩展到可用硬件。我是说,谁都能创造百万以上只猴子,但是那种超过12个处理器并行的循环就需要人才了,对吗?好吧,多少是有点技术含量的。.NET的并行功能已经为你准备好大部分内容了,这才是重点。它是为大量内容而设的并行进程。

我们创建了一个此应用程序的WinForm版本,我们用它来展示在.NET上的并行计算。然后Paul Batum和我上周参加了keeping It Realtime会议,会议上展示了SignalR。我不想再做相同的那种“这是real-time聊天应用程序”或者“这里是一张图表,展示了real-time的结果”这类演示,当然大家都习惯在这种场合做这类东西。我认为我们可以把WinForm莎士比亚猴子演示移植到ASP.NET和SignalR中,这也是Paul正准备着手的内容。

Looks like 80,000 generations of monkeys

在做这类疯狂的密集运算时,还需要返回real-time结果,你可能会在real-time通知部分运用节点e,然后产生另一个进程,使用C或者其他数学功能,然后让它们互相交流。我们喜爱节点,你可以在IIS上运行节点,或者甚至在 WebMatrix中编写节点。不过,节点有所长,.NET也有所长。

比如,.NET很擅长CPU-bound的密集运算,好比在F#中做并行矩阵乘法。ASP.NET擅长扩展像Bing或者StackOverflow这种网站。说起real-time的时候,你可能不会想到IIS和ASP.NET,但是在使用长轮询以及在实验室中使用像拥有.NET4.5WebSocket支持的 WebSockets 高效协议时,SignalR使用异步处理器和智能技术能获取很棒的扩展。

所以,我们想看看你是否绑定异步背景工作,是否使用了尽可能多的处理器,是否通过SignalR的长轮询或者WebSocket获取real-time的状态更新,以及是否使用C#,.NET, ASP.NET和IIS。

它每秒在成千上万种猴子种类中选取8万种(每种大约200只猴子)来获取哈姆雷特的开场白。所以那就是1600万只猴子来获取文本,正如他们所说,有那么多猴子。

这就是应用程序的整体想法。客户端非常轻量级。只有两个框,两个按钮,一个复选框以及一些文本,包含了一些常用事件,比如运行,取消,完成和更新进程,不过你可以通过$.connection.monkeys看看猴子有什么不同,当然只要关掉$.connection,也可以通过$.connection.foo查看。

这些功能是客户端上的,但是我们通过持续连接在服务器上使用它们,然后更新文本。

 1: <script src="Scripts/jquery-1.6.4.min.js"></script> 
 2: <script src="Scripts/json2.min.js"></script>
 3: <script src="Scripts/jquery.signalR.min.js"></script>
 4: <script src="signalr/hubs"></script>
 5: <script>
 6: $(function () {
 7: $('#targettext').val('To be or not to be, that is the question;\nWhether \'tis nobler in the mind to suffer\n\The slings and arrows of outrageous fortune,\n\Or to take arms against a sea of troubles,\n\And by opposing, end them.');
 8: var monkeys = $.connection.monkeys,
 9: currenttext = $('#currenttext'),
 10: generationSpan = $('#generation'),
 11: gpsSpan = $('#gps');
 12: monkeys.updateProgress = function (text, generation, gps) {
 13: currenttext.val(text);
 14: generationSpan.text(generation);
 15: gpsSpan.text(gps);
 16: };
 17: monkeys.started = function (target) {
 18: $('#status').text('Working...');
 19: $('#targettext').val(target);
 20: $('#cancelbutton').removeAttr('disabled');
 21: };
 22: monkeys.cancelled = function () {
 23: $('#status').text('Cancelled');
 24: $('#cancelbutton').attr('disabled', 'disabled');
 25: };
 26: monkeys.complete = function () {
 27: $('#status').text('Done');
 28: $('#cancelbutton').attr('disabled', 'disabled');
 29: };
 30: $.connection.hub.start({}, function () {
 31: $('#startbutton').click(function (event) {
 32: $('#status').text('Queued...');
 33: monkeys.startTyping($('#targettext').val(), $('#isparallel').is(':checked'));
 34: });
 35: $('#cancelbutton').click(function (event) {
 36: monkeys.stopTyping();
 37: });
 38: });
 39: });
 40: </script>
 41: 

使用$.connection.hub.start后,神奇的一刻发生了。中心客户端代码实际是在~/signalr/hubs中的。看看它是怎么包含在顶端的。客户端代理是根据服务器端的集线器生成的。

服务器端的结构如下所示:

 1: [HubName("monkeys")]
 2: public class MonkeyHub : Hub
 3: {
 4: public void StartTyping(string targetText, bool parallel)
 5: {
 6: }
 7: public void StopTyping()
 8: {
 9: }
 10: } 

StartTyping和StopTyping.NET方法是可以从客户端通过猴子JavaScript对象来调用的。所以你可以从客户端JavaScript调用服务器端C#,从C#服务器你可以调用客户端上的JavaScript方法。如果你对它进行调试,然后看看线路上的状况,会很有意义。关键是C#和Json对象可以来回流动,这样会模糊客户端和服务器间的界限。在配置上没什么创新。那就是我们如何在客户端和服务器之间交流的。现在,那些猴子们怎么样了?

你可以查看完整代码,但是StartTyping就偏离了。注意它是如何持续报告给集线器(调回客户端)的。Paul正在使用Hub.GetClients来和所有连接的客户端进行交流。当前只支持每次一只猴子工作。其他连接的客户端可以看到这项工作的进展。

 1: public void StartTyping(string targetText, bool parallel)
 2: {
 3: var settings = new GeneticAlgorithmSettings { PopulationSize = 200 };
 4: var token = cancellation.Token;
 5:  
 6: 
 7: currentTask = currentTask.ContinueWith((previous) =>
 8: {
 9: // Create the new genetic algorithm
 10: var ga = new TextMatchGeneticAlgorithm(parallel, targetText, settings);
 11: TextMatchGenome? bestGenome = null;
 12: DateTime startedAt = DateTime.Now;
 13:  
 14: Hub.GetClients<MonkeyHub>().started(targetText);
 15:  
 16: // Iterate until a solution is found or until cancellation is requested
 17: for (int generation = 1; ; generation++)
 18: {
 19: if (token.IsCancellationRequested)
 20: {
 21: Hub.GetClients<MonkeyHub>().cancelled();
 22: break;
 23: }
 24:  
 25: // Move to the next generation
 26: ga.MoveNext();
 27:  
 28: // If we've found the best solution thus far, update the UI
 29: if (bestGenome == null ||
 30: ga.CurrentBest.Fitness < bestGenome.Value.Fitness)
 31: {
 32: bestGenome = ga.CurrentBest;
 33:  
 34: 
 35:  
 36: int generationsPerSecond = generation / Math.Max(1, (int)((DateTime.Now - startedAt).TotalSeconds));
 37: Hub.GetClients<MonkeyHub>().updateProgress(bestGenome.Value.Text, generation, generationsPerSecond);
 38:  
 39: if (bestGenome.Value.Fitness == 0)
 40: {
 41: Hub.GetClients<MonkeyHub>().complete();
 42: break;
 43: }
 44: }
 45: } 
 46:  
 47: }, TaskContinuationOptions.OnlyOnRanToCompletion);
 48:  
 49: }

如果他愿意,他可以使用.Caller来和调用StartTyping的特定客户端进行交流。在ga.MoveNext中我们决定用并行,或者不基于该复选框。这就是我们随机选取高质配种猴来孕育未来猴子的地方。期望它们会输出像莎士比亚的作品,而不是普通的表达。

通过简单地把Enumerable.Range变为ParallelEnumerable.Range,我们可以开始做简单的并行,还可以使用机器上的处理器。注意代码是一样的。

 1: private TextMatchGenome[] CreateNextGeneration()
 2: {
 3: var maxFitness = _currentPopulation.Max(g => g.Fitness) + 1;
 4: var sumOfMaxMinusFitness = _currentPopulation.Sum(g => (long)(maxFitness - g.Fitness));
 5:  
 6: if (_runParallel)
 7: {
 8: return (from i in ParallelEnumerable.Range(0, _settings.PopulationSize / 2)
 9: from child in CreateChildren(
 10: FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),
 11: FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))
 12: select child).
 13: ToArray();
 14: }
 15: else
 16: {
 17: return (from i in Enumerable.Range(0, _settings.PopulationSize / 2)
 18: from child in CreateChildren(
 19: FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness),
 20: FindRandomHighQualityParent(sumOfMaxMinusFitness, maxFitness))
 21: select child).
 22: ToArray();
 23: }
 24: }
 25: 

我12个处理器的桌面用并行在一秒内做了3800个品种。

Hexacore Super Computer!

非常感谢Paul为SignalR提供了可爱的端口,还要感谢Stephen Toub的算法。

在我的BitBucket上有SignalR猴子演示的代码。现在它需要.NET 4.5和Visual Studio开发者预览版,不过你可以删去几行,然后在.NET 4上运行,这是完全没有问题的。

注意SignalR可以在.NET 4及以上版本上运行,你今天就可以试试了。你还可以登陆http://chatapp.apphb.com,在SignalR 聊天应用程序里的“aspnet”房间和开发者聊天。你只要给自己取个昵称,然后加入aspnet就可以了。

在我写这篇博客的时候,没有猴子受伤。

Leave a Comment
  • Please add 8 and 3 and type the answer here:
  • Post