I was playing with this with large values for width and height and found that I could get a 5 fold decrease in runtime by replacing the last for loop with this:

for (1..$high) {
   print "$str\n";

   $prev_str = substr($str, -1, 1) . $str .  substr($str, 0, 1);

   $str = '';

   for ($i = 0; $i < $wide; $i++) {
      $str .= $rules{substr($prev_str, $i, 3 )};
   }
}
[download]